Sorted GCD Pair Queries, Excellent C++ Solution explained
Do Upvote If Found Helpful !!!ApproachThe problem here is quite interesting and needs a bit of understanding of basic number theory like GCD and Prime Numbers.
***Do Upvote If Found Helpful !!!***

# Approach
The problem here is quite interesting and needs a bit of understanding of basic number theory like **GCD** and **Prime Numbers**. Lets first get over with brute force approach : Iterate over all possible pairs, find all gcds sort them and get your answer ! Yeeee but no **TLE and MLE** await for you at door ! So then what next should we do ?
    
Lets look at the problem from another perspective. Instead of calculating pairwise GCD, lets say I have a number **x**, I want to find the number of pairs that have **GCD = x** or **PairsGCD(x)**. So now instead of doing all pairwise operations, we iterate over all possible values that GCD can take i.e from **1 to Max(Nums)**. For each value in this range, we calculate **PairsGCD(i)** and store it in some array. But how exactly do you find these count of pairs ?

Lets say there are **cnt[i]** numbers in array nums that are divisible by **i**, then **PairsGCD(i) = (cnt[i] * (cnt[i] - 1)) / 2** or is there still a flaw in this formula or equation ? Is this equation complete ? Turns out we missed to account for numbers when **multiples of i are multiples of each other too !**. For example, lets say **i = 3**, then 6 and 12 are both divisible by 3 but the GCD of this pair is not 3 but 6 instead cause 12 is a multiple of 6 too. So then how do we handle this problem cause there are a lot of such multiples. Turns out we can simply subtract the value of **PairsGCD(i * k)** for all **k = 2, 3, 4, ... Max(Nums)/i** from **PairsGCD(i)** to remove these redundant incorrect pairs ! Wow quite elegant !

    PairsGCD[i] = (divcnt[i] * (divcnt[i] - 1)) / 2  -  ∑ PairsGCD[i * k] , k = 2, 3, .. , max(nums)/i

So here's what we do, we run a loop backwards starting from **Max(Nums)** because for any **i**, we need the info of all its multiples. Therefore we move backward calculating these values. We maintain the count array that intially stores count of all values in nums. Then for each number **i**, we iterate over its possible multiples until max(nums) and accumulate of PairsGCD values and frequency of those multiples in nums array. At end of this loop, we just update the value of **PairsGCD[i]** as per the above equation. This complete process takes **O(Max*log(Max))** time.

Now you just create a prefix sum array using PairsGCD array and do binary search for each query to find what GCD is present at queried index ! Simple Right ? Implementation goes below:

# Complexity
- Time complexity: **O(Max * log(Max) + Q * log(Max))**
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: **O(Max)**
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    #define ll long long
    vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {

        ll mx = *max_element(nums.begin(),nums.end()), n = nums.size(), s = 0;
        vector<ll>cnt(mx+1,0), gcdp(mx+1,0);

        for(auto x : nums){
            cnt[x]++;
        }

        for(ll i = mx; i > 1; i--){
            ll total = 0, cntl = cnt[i];
            for(ll j = 2 * i; j <= mx; j += i){
                cntl += cnt[j];
                total += gcdp[j];
            }
            gcdp[i] = (cntl * (cntl - 1LL)) / 2 - total;
            s += gcdp[i];
        }
        gcdp[1] = (n * (n - 1)) / 2 - s;
        
        for(ll i = 1; i <= mx; i++){
            gcdp[i] += gcdp[i-1];
        }

        vector<int>ans;
        for(auto x : queries){
            ll start = 1, end = mx, mid, val = -1;
            while(start <= end){
                mid = start + (end - start) / 2;
                if(gcdp[mid] >= x + 1){
                    val = mid;
                    end = mid - 1;
                }
                else{
                    start = mid + 1;
                }
            }
            ans.push_back(val);
        }

        return ans;
    }
};
```
['Math', 'Number Theory', 'C++']