[Python] Counting/Sieve
Motivated by the small limit for A[i], we want countG[g] = the number of pairs (i < j) with gcd(A[i], A[j]) == g.  After, it is easy to use a binary search on t
Motivated by the small limit for `A[i]`, we want `countG[g]` = the number of pairs (`i < j`) with `gcd(A[i], A[j]) == g`.  After, it is easy to use a binary search on the cumulative sums of countG to answer each query.\n\nLet `c = countD[d]` be the number of `i` with `A[i] % d == 0`.  Then there are `c * (c-1) / 2` pairs that have a gcd `g` that is a multiple of `d`.  We can subtract these mulitples to calculate the number of pairs with a gcd that is exactly `d`.\n\n# Code\n```python3 []\nMX = 50001\ndivisors = [[] for _ in range(MX)]\nfor x in range(1, MX):\n    for y in range(x, MX, x):\n        divisors[y].append(x)\n\n\nclass Solution:\n    def gcdValues(self, A: List[int], queries: List[int]) -> List[int]:\n        M = max(A)\n        countA = Counter(A)\n        countD = Counter()  # countD[d]: number of (i) with A[i] % d == 0\n        for x, freq in countA.items():\n            for d in divisors[x]:\n                countD[d] += freq\n\n        countG = Counter()  # countG[g]: number of (i < j) with gcd(A[i], A[j]) == g\n        for g in range(M, 0, -1):\n            c = countD[g]\n            if c <= 1:\n                continue\n            countG[g] = c * (c - 1) // 2\n            countG[g] -= sum(countG[x] for x in range(2 * g, M + 1, g))\n\n        glist = [g for g, v in reversed(countG.items())]\n        vlist = [v for g, v in reversed(countG.items())]\n        Pvlist = list(accumulate(vlist))\n\n        ans = []\n        for q in queries:\n            i = bisect_left(Pvlist, q + 1)\n            ans.append(glist[i])\n        return ans\n\n```
['Python3']