Python easiest solution beats 100% of users
Intuition\nIf we can somewhow for each g, find the number of pairs whose gcd = g, then we are done. Please take a moment to think why tha is true.\n\n# Approach
# Intuition\nIf we can somewhow for each g, find the number of pairs whose gcd = g, then we are done. Please take a moment to think why tha is true.\n\n# Approach\nMobius inversion finds number of pairs whose gcd = g, in O(n / g). So now, all we have to do, is run the mobius on all g. As you might have guessed, that function converges towards nlog(n)\n\n# Complexity\n- Time complexity:\nO(nlog(n) + qlog(q))\n\n- Space complexity:\nO(maxN) where maxN is the maximum element that is in nums\n\n# Code\n```python3 []\nclass Solution:\n    def gcdValues(self, nums, queries):\n        mxN = max(nums) + 10\n        mob = [0] * mxN\n        sve = [0] * mxN\n        cnt = [0] * mxN\n        mob[1] = 1\n\n        for num in nums:\n            cnt[num] += 1\n\n        for i in range(1, mxN):\n            sve[i] += cnt[i]\n            for j in range(2 * i, mxN, i):\n                mob[j] -= mob[i]\n                sve[i] += cnt[j]\n\n        def solve(i):\n            return sum(mob[j // i]  * sve[j] * (sve[j]-1) // 2 for j in range(i, mxN, i))\n\n        \n        ans = [0] * len(queries)\n        q = sorted([(queries[i], i) for i in range(len(queries))])\n\n        i, j, cur = 1, 0, solve(1) - 1\n\n        while j < len(q):\n            while cur < q[j][0]:\n                i += 1\n                cur += solve(i)\n            ans[q[j][1]] = i\n            j += 1\n\n        return ans\n```
['Python3']