[Python3] accumulate + binary search (18 lines, easy to read)
Intuition\n Describe your first thoughts on how to solve this problem. \nNotice that nums[i] <= 5 * 10^4 which is a small range. Thus, the distinct divisors are
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nNotice that `nums[i] <= 5 * 10^4` which is a small range. Thus, the distinct divisors are not too many.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can count the divisors of every number. Each common divisor pairs number is `n * (n - 1) // 2`. Since we should only count GCD, we can iterate the divisors from large to small, and deduct the counted `gcdPairs` from the sub-divisors.\n\nFor queries, we can accumulate the `gcdPairs` from small to large and use bisect to find the answer.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n`O(nums[i] * log(nums[i]) + queries.length * log(nums[i]))`\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n`O(nums[i])`\n\n# Code\n```python3 []\nN = 50001\ndivs = [[] for _ in range(N)]\nfor i in range(1, N):\n    for j in range(i, N, i):\n        divs[j].append(i)\n    \nclass Solution:\n    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:\n        c = Counter(chain.from_iterable(divs[ni] for ni in nums))\n        gcds = defaultdict(int)\n        for f in sorted(c.keys(), reverse=True):\n            nf = gcds[f] = gcds[f] + c[f] * (c[f] - 1) // 2\n            if not nf:\n                del gcds[f]\n                continue\n            for ff in divs[f]:\n                gcds[ff] -= nf\n            gcds[f] = nf\n        gcd_i = sorted(gcds.keys())\n        gcd_ac = list(accumulate(gcds[i] for i in gcd_i))\n        return [gcd_i[bisect_right(gcd_ac, q)] for q in queries]\n\n```
['Python3']