[Java/C++/Python] Sieve
Explanation\n\n1. Counting Frequencies\n\ncnt counts the frequency of A[i]\n\n2. Calculating GCD\n\nIterates through all possible numbers a,\nfrom the max(A) do
# **Explanation**\n\n1. Counting Frequencies\n\n`cnt` counts the frequency of `A[i]`\n\n2. Calculating GCD\n\nIterates through all possible numbers `a`,\nfrom the `max(A)` down to `1`.\n\nCount the number of multiplers of `a`,\n`mul = cnt[a] + cnt[2a] + ...`\n\nThe gcd of a-multiplers, will still be a-multipler.\nThere will be `mul * (mul - 1) / 2` pairs.\nthen we exclude the count of gcd that are a-multiplers.\n\n`gcd[a] = mul * (mul - 1) / 2 - gcd[2a] - gcd[3a] ...`\n\n3. Prefix Sum\n\nIt calculates the prefix sum of the GCD counts.\nThis allows for quick lookup\nof the accumulated count of GCDs\n(less than or equal to a given value).\n\n4. Binary Search\n\nFor each query `q`,\nuse binary search on the prefix sum.\n<br>\n\n# **Summary by gpt**\nIn essence, the solution avoids explicitly\ngenerating and sorting all the GCD pairs,\nwhich would be inefficient.\n\nInstead, it cleverly uses frequency counting,\ndivisor analysis, prefix sums, and binary search\nto achieve a more optimized solution.\n\n**Upvote it to learn it!**\n<br>\n\n# **Complexity**\nTime `O(mlogm + qlogm)`\nSpace `O(m + q)`\n<br>\n\n**Python**\n```py\n    def gcdValues(self, A: List[int], queries: List[int]) -> List[int]:\n        m = max(A)\n        cnt = Counter(A)\n        gcd = [0] * (m + 1)\n\n        for a in range(m, 0, -1):\n            mul = sum(cnt[b] for b in range(a, m + 1, a))\n            gcd[a] = mul * (mul - 1) // 2\n            gcd[a] -= sum(gcd[b] for b in range(a * 2, m + 1, a))\n\n        gcd = list(accumulate(gcd))\n        return [bisect_right(gcd, q) for q in queries]\n```\n\n**Java**\n```java\n    public int[] gcdValues(int[] A, long[] queries) {\n        int m = Arrays.stream(A).max().getAsInt();\n        Map<Integer, Integer> cnt = new HashMap<>();\n        for (int a : A) {\n            cnt.put(a, cnt.getOrDefault(a, 0) + 1);\n        }\n\n        long[] gcd = new long[m + 1];\n        for (int a = m; a > 0; --a) {\n            long mul = 0;\n            for (int b = a; b <= m; b += a) {\n                mul += cnt.getOrDefault(b, 0);\n            }\n            gcd[a] = mul * (mul - 1) / 2;\n            for (int b = a * 2; b <= m; b += a) {\n                gcd[a] -= gcd[b];\n            }\n        }\n\n        for (int i = 1; i <= m; ++i) {\n            gcd[i] += gcd[i - 1]; // Prefix sum\n        }\n\n        int qn = queries.length, res[] = new int[qn];\n        for (int i = 0; i < qn; i++) {\n            res[i] = upper_bound(gcd, queries[i]); // find upper bound;\n        }\n        return res;\n    }\n\n    private int upper_bound(long[] arr, long target) {\n        int left = 0, right = arr.length;\n        while (left < right) {\n            int mid = left + (right - left) / 2;\n            if (arr[mid] <= target) {\n                left = mid + 1;\n            } else {\n                right = mid;\n            }\n        }\n        return left;\n    }\n```\n\n**C++**\n```cpp\n    vector<int> gcdValues(vector<int>& A, vector<long long>& queries) {\n        int m = *max_element(A.begin(), A.end());\n        unordered_map<int, int> cnt;\n        for (int a : A) {\n            cnt[a]++;\n        }\n\n        vector<int> gcd(m + 1);\n        for (int a = m; a > 0; --a) {\n            long long mul = 0;\n            for (int b = a; b <= m; b += a) {\n                mul += cnt[b];\n            }\n            gcd[a] = mul * (mul - 1) / 2;\n            for (int b = a * 2; b <= m; b += a) {\n                gcd[a] -= gcd[b];\n            }\n        }\n\n        partial_sum(gcd.begin(), gcd.end(), gcd.begin()); // prefix sum\n        vector<int> res;\n        for (int q : queries) {\n            res.push_back(upper_bound(gcd.begin(), gcd.end(), q) - gcd.begin());\n        }\n        return res;\n    }\n```\n
['C', 'Python', 'Java']