Count pairs with GCD x using Sieve DP
\nclass Solution:\n    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:\n        M = max(nums)\n        ctr = [0] * (M + 1)\n        for e
```\nclass Solution:\n    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:\n        M = max(nums)\n        ctr = [0] * (M + 1)\n        for el in nums:\n            ctr[el] += 1\n        mctr = [0] * (M + 1)\n        for i in range(1, M + 1):\n            mul = 1\n            while i * mul <= M:\n                mctr[i] += ctr[i * mul]\n                mul += 1\n        dp = [0] * (M + 1)\n        for i in range(M, 0, -1):\n            dp[i] = mctr[i] * (mctr[i] - 1) // 2\n            mul = 2\n            while i * mul <= M:\n                dp[i] -= dp[i * mul]\n                mul += 1\n        q = len(queries)\n        queries = [(queries[i], i) for i in range(q)]\n        queries.sort()\n        res = [0] * q\n        i = 0\n        less = 0\n        for pos, qpos in queries:\n            while i <= M and less + dp[i] <= pos:\n                less += dp[i]\n                i += 1\n            res[qpos] = i\n        return res\n```
['Python']