Python Hard
python3 []\n\nMX = 50005\n\nD = [set()]\n\nfor i in range(1, MX + 1):\n    divisors = set()\n    divisors.add(1)\n\n    for j in range(2, ceil(math.sqrt(i)) + 1
```python3 []\n\nMX = 50005\n\nD = [set()]\n\nfor i in range(1, MX + 1):\n    divisors = set()\n    divisors.add(1)\n\n    for j in range(2, ceil(math.sqrt(i)) + 1):\n        if i % j == 0:\n            divisors.add(j)\n            divisors.add(i//j)\n\n    if i > 1:\n        divisors.add(i)\n        \n    D.append(divisors)\n    \n\n\nclass Solution:\n    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:\n        lookup = Counter(nums)\n        nx = max(nums)\n\n        count = [0] * (nx + 1)\n        for key, val in lookup.items():\n            for d in D[key]:\n                count[d] += val\n\n        \n        mp = [0] * (nx + 1)\n        for i in range(nx, 0, -1):\n            mp[i] = (count[i] * (count[i] - 1)) // 2\n\n            j = i + i\n            while j <= nx:\n                mp[i] -= mp[j]\n                j += i\n        \n\n        pref = [0]\n\n        for x in mp:\n            pref.append(pref[-1] + x)\n\n        ans = []\n\n        for x in queries:\n            index = bisect.bisect_right(pref, x) - 1\n            ans.append(index)\n\n        return ans\n        \n\n\n        \n\n        \n```
['Python3']