Near Linear - O(MAX log MAX + Q log Q + N)
Intuition/Approach\n\nHuge thanks to this problem: https://leetcode.com/problems/find-the-number-of-good-pairs-ii/ and a friend of mine for first introducing me
# Intuition/Approach\n\nHuge thanks to this problem: https://leetcode.com/problems/find-the-number-of-good-pairs-ii/ and a friend of mine for first introducing me to this trick (see solutions within the top 0.19%, not the editorials).\n\nFor this problem, it has a similar concept to the solution above. But first, let\'s first look at what it means to be in the $k^{th}$ position of the `gcdPair` array. That basically just means there are $k - 1$ other pairs which have a gcd less. So now all we have to do is find a way to calculate the number of gcds under some number $x$. So we can change this problem into something simpler: calculate the number of pairs of numbers which have a gcd of `g` and store that in `count[g]`. How do we do that?: \n\nNow for the trick: when you are looking at common factors of numbers, it is often better to look at multiples as you can use the sieve of eratosthenes trick of bounding the complexity by $(n + n/2 + n/3 + ...)$. We can do the same here, first let us count all the numbers in `nums` which are multiples of some number $g$, we can do this by iterating over g, 2g, ... and for each of those adding the frequency of that number `freq[kg]`. Store the number of multiples of $g$ in `#multiples[g]`.\n\nWe know that the number of pairs of numbers which have a gcd of g (that is `count[g]`) is equal to all the ways we can pair up multiples of g, which is `#multiples[g] * (#multiples[g] - 1) / 2`, minus the number of things which might have a greater gcd (subtract off count[x] if g < x and x divides g).\n\nThat\'s it! Then at the end we can either do a two pointers or binary search on the prefix sum of `count[g]`.\n\n# Complexity\n- Time complexity:\n$\\mathcal{O}(\\text{MAX} \\log \\text{MAX} + Q \\log Q + N)$\n\n# Code\n```cpp []\ntypedef long long ll;\nclass Solution {\npublic:\n    vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {\n        int MAX = 50000;\n        vector<ll> freq(MAX+1, 0);\n        for(auto x: nums) freq[x]++;\n        vector<ll> multiples(MAX+1, 0);\n        for(int g=1; g<=MAX; g++) {\n            for(int k=g; k<=MAX; k+=g) multiples[g] += freq[k];\n        }\n        vector<ll> count(MAX+1, 0);\n        for(int g=MAX; g>=1; g--){\n            if(multiples[g] < 2){\n                count[g]=0;\n                continue;\n            }\n            count[g] = multiples[g]*(multiples[g]-1)/2;\n            for(int k=2*g; k<=MAX; k+=g){\n                count[g] -= count[k];\n            }\n        }\n        int qn = queries.size();\n        vector<pair<ll, int>> qs;\n        for(int i=0;i<qn;i++) qs.emplace_back(queries[i], i);\n        sort(qs.begin(), qs.end());\n        vector<int> answer(qn);\n        ll total =0;\n        int g=1;\n        int current =0;\n        while(g<=MAX && current < qn){\n            total += count[g];\n            while(current < qn && qs[current].first < total){\n                answer[qs[current].second] = g;\n                current++;\n            }\n            g++;\n        }\n        return answer;\n    }\n};\n\n```
['C++']