Dynamic Programming + Binary Search
Approach\n\nFirst, let $M = \max(nums)$. For each unique number $m=1...M$, we let $count[m]$ count how many numbers in nums it divides. \n\nNow let $dp[i]$ be t
# Approach\n\nFirst, let $M = \\max(nums)$. For each unique number $m=1...M$, we let $count[m]$ count how many numbers in nums it divides. \n\nNow let $dp[i]$ be the number of pairs with gcd EXACTLY $i$. Then we have \n\n$$dp[i] = {count[i] \\choose 2} - dp[2i] - dp[3i] - ....$$\n\nThis is because we count all pairs from $count[i]$ except the ones with gcd a multiple of $i$\n\nFinally, we let $gcds$ be the numbers $i$ with $dp[i]>0$. And we build a prefix array for the count of pairs with gcd $\\leq gcds[i]$. \n\n# Code\n```python3 []\nclass Solution:\n    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:\n        M = max(nums)\n        \n        count = [0 for _ in range(M+20)]\n        for n in nums:\n            x = 1\n            while x*x <= n:\n                if n%x==0:\n                    count[x]+=1\n                    if x*x!=n:\n                        count[n//x]+=1 \n                x+= 1\n        \n        dp = [0 for _ in range(M+1)] \n        for i in range(M, 0, -1):\n            dp[i] = count[i]*(count[i]-1)//2\n            #now subtract\n            j = 2\n            while i*j <= M:\n                dp[i] -= dp[i*j]\n                j+=1 \n        gcds = [i for i in range(M+1) if dp[i]>0]\n        sm = [dp[i] for i in range(M+1) if dp[i]>0]\n        for i in range(1, len(sm)):\n            sm[i] += sm[i-1]\n        \n        out = []\n        for q in queries:\n            i = bisect.bisect_left(sm, q+1)\n            out.append(gcds[i])\n        return out\n```
['Python3']