Ling
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:\n        #gcd\u95EE\u9898 -- find\uFF08\u679A\u4E3E\uFF09 gcd and multiple of gcp\n        #gcd = 2 -- we only need see multiple of 2 -- 5 even number select 2 -- C(5,2)\n        #if gcd(8,16) = 8\n        #cnt_gcd[2] = C(\u5076\u6570\u4E2A\u6570\u53732\u7684\u500D\u6570\uFF0C2) - cnt_gcd[4] - cnt_gcd[6] - ...\n        #cnt_gcd[i] = C(i\u7684\u500D\u6570\uFF0C2) - cnt_gcd[2i] - ....\n        #\u5148\u6709\u540E\u9762\u7684\u624D\u6709\u524D\u9762\u7684\u6240\u4EE5 \u4ECE\u540E\u5411\u524D from end to start\n        mx = max(nums)\n        cnt_x = [0] * (mx + 1)\n        for x in nums:\n            cnt_x[x] += 1\n            \n        cnt_gcd = [0] * (mx + 1)\n        for i in range(mx, 0, -1):\n            c = 0\n            for j in range(i, mx + 1, i):\n                c += cnt_x[j]\n                cnt_gcd[i] -= cnt_gcd[j]  # gcd \u662F 2i,3i,4i,... \u7684\u6570\u5BF9\u4E0D\u80FD\u7EDF\u8BA1\u8FDB\u6765 -- we need to minor 2i, 3i,\n            cnt_gcd[i] += c * (c - 1) // 2  # c \u4E2A\u6570\u9009 2 \u4E2A\uFF0C\u7EC4\u6210 c*(c-1)/2 \u4E2A\u6570\u5BF9\n\n        s = list(accumulate(cnt_gcd))  # \u524D\u7F00\u548C prefix\n        return [bisect_right(s, q) for q in queries]\n\n\n```
['Python3']