Detailed explanation along With C++ Code. 
IntuitionThis problem is a mix of inclusion exclusion principle as well as sieve of erastosthenes. Here as we know we cannot find the entire gcd array as it wou
# Intuition
This problem is a mix of **inclusion exclusion principle** as well as **sieve of erastosthenes**. Here as we know we cannot find the entire gcd array as it would definitely exceed the time limit because it will go to n*(n-1)/2. So we use multiple arrays to keep track of which element comes how many times in the hypothetical gcd array and return the answer using *binary seach on answers* 

---


# Approach
**Step 1:** We first of all create an arrays named *freq* of size equal to the *maximum element* in nums (i.e the given array)

**Step 2:** We store the *frequency count* of each element in our *freq* array 

**Step 3:** We then create a *multiples* array which will store how many **multiples** of each element are present in nums

**Step 4:** We convert this multiples array from storing the *count of multiples* to the array which will now store the *number of pairs whose gcd can be this element*.

***For ex***: let us say there are 6 multiples of 2 in nums. Since all these 6 numbers are divisible by 2, the pairs formed among them can have their gcd as 2. That is why we store the no. of pairs i.e 6C2
whose gcd can be 2.

**Step 5:** Now why did i say can be gcd. Because say there are 10 pairs whose gcd can be 2, but out of those 10 pairs , their can be 4 pairs(just for example), whose gcd is a multiple of 2 i.e say 6. 
So those pairs have to be removed from the counting of 2. This is the reason why we again use a sieve like approach to exclude the pairs for each count

**Step 6:** Then we create a *prefix array* which will just store the prefix sums. If you have understood the solution till here, you would know we can't respond to each query by iterating over our multiples array, so we will use this pref array and get each query in log(N) time.

---



# Complexity
Say X is the maximum element in nums. 
# - Time complexity:O(XlogX)
       


# - Space complexity:O(X)


---


# Code
```cpp []
class Solution {

public:
    typedef long long ll;
    vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {
        ll n=nums.size();
        ll vals=*max_element(nums.begin(),nums.end());
        vector<ll>freq(vals+1,0);
        for(int i=0;i<n;i++){
            freq[nums[i]]++;
        }
        vector<ll>multiples(vals+1,0);
        
        for(int i=1;i<=vals;i++){
            for(int j=i;j<=vals;j+=i){
                multiples[i]+=freq[j];
            }
        }
        for(int i=1;i<=vals;i++){
            ll x=multiples[i];
            multiples[i]=(x*(x-1)*1ll)/2;
        }
        for(int i=vals;i>=1;i--){
            for(int j=2*i;j<=vals;j+=i){
                multiples[i]-=multiples[j];
            }
        }
        vector<ll>pref(vals+1,0);
        for(int i=1;i<=vals;i++){
            pref[i]=pref[i-1]+multiples[i];
            cout<<pref[i]<<endl;
        }
        vector<int>ans;
        for(int i=0;i<queries.size();i++){
            ll q=queries[i]+1;
            auto it=lower_bound(pref.begin(),pref.end(),q);
            ll dis=it-pref.begin();
            
            ans.push_back(dis);
        }
        return ans;

    }
};
```


# If you understood the solution in detail, Do UPVOTE!!
['Array', 'Hash Table', 'Binary Search', 'Combinatorics', 'Counting', 'C++']