Comments and Dry Run
Intuition\nSolved post contest after understanding solution mentioned in the followinf link:\n# Approach\nhttps://leetcode.com/problems/sorted-gcd-pair-queries/
# Intuition\nSolved post contest after understanding solution mentioned in the followinf link:\n# Approach\nhttps://leetcode.com/problems/sorted-gcd-pair-queries/solutions/5875685/c-divisors-counting-and-binary-search-o-n-sqrt-maxelement-easy-to-understand/\nI have just tried to explain in my way using a dry example. For detailed explanation of the steps, please refer the link above.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {\n       \n\n        //DRY RUN: assume nums is [2,4,14,7,28] \n        int maxi = nums[0];\n        \n        for(int i : nums){\n            if(i > maxi) maxi = i;\n        }\n        // stores the number of elements in nums which have divisor i\n        // divisorCount[i] -> represents the number of elements in nums having i as the divisor\n        vector<int> divisorCount(maxi + 1 , 0);\n        for(int i = 0; i < nums.size(); i++)\n        {\n            int curr = nums[i];\n           // cout << curr << " " << sqrt(curr) << endl;\n            for(int j = 1; j <= floor(sqrt(curr)); j++)\n            {\n                //cout << "i:" << i << " j" << j << endl;\n                if(curr%j == 0){\n                    divisorCount[j] += 1;\n                    //cout << "i:" << i << " j" << j << " diivosr:" << j << " dc:" << divisorCount[j] << endl;\n\n                    if(j != (curr/j)) divisorCount[curr/j] += 1;\n                }\n            }\n        }\n        //for(int i = 0; i < maxi; i++) cout <<divisorCount[i] << " " ;\n        //DRY RUN ->  divisorCount will be [0, 5, 4, 0, 2,...3, ...2, ...1]\n                           //indices:      [0, 1, 2, 3, 4,...7, ...14, ...28]\n                           // it means 1 divides 5 numbers in nums, 2 divides 4 numbers in nums , 7 divides 3 numbers in nums\n\n\n\n        //stores the number of pairs of elements in nums having gcd g\n        // gcdCount[i] -> stores the number of pairs of elements in nums having gcd as equal to i\n        vector<long long> gcdCount(maxi + 1, 0);\n\n        for(int i = maxi; i > 0; i--){\n            //gcd is i, we need to find number of pairs in nums having gcd i\n\n            // number of pairs having gcd as i is equal to cntDivisors[i] C 2 or cntDivisors[i]*(cntDivisors[i] - 1) / 2\n            long long cnt  = divisorCount[i] ;\n            gcdCount[i] = (cnt * (cnt - 1))/2;\n            \n            // after the above step \n            // DRY RUN: --> gcdCount will be [0, 10, 6, 0, 1,...3,...1,....0]\n            //              indices will be  [0, 1, 2, 3, 4,...7,...14,...28]\n            // meaning number of pairs in nums hacing gcd 7 is 3, number of pairs in nums having gcd as 2 is 6    \n\n            // this also includes other pairs, so we ned to exclude those whose gcd is 2g, 3g, 4g, 5g..so on until maxi\n            // for example, while counting number of pairs whose gcd is 7 we did 3C2. which means we selected all 3 pairs from {7,14,28} namely (7,14) ; (14,28) and (7,28) . the middle pair\'s gcd is not 7 but 14. so we need to remove that pair and hence subtract those.\n            //another example while counting number of pairs whose gcd is 2 we did 4C2. which means we selected all 6 pairs from {2,4,14,28} namely (2,4), (2,14) (2,28) ; (4,14), (4,28), (14,28). (4,28) gcd is not 2 but 4. (14,28) gcd is not 2 but 14. So we need to remove that pair and hence subtract those.\n            for(int j = 2*i ;j <= maxi; j+=i){\n                gcdCount[i] -= gcdCount[j];\n            }\n            // after the above step \n            // DRY RUN: --> gcdCount will be [0, 2, 4, 0, 1,...2,...1,....0]\n            //              indices will be  [0, 1, 2, 3, 4,...7,...14,...28]\n            // meaning gcd of 2 pairs is \n        }\n\n        // once we have count of all pairs whose gcd is g it becomes simpler. if someone asks what is gcd of rank 5th pair.\n        // we iterate through the array see how many elements come up before sm > 5.\n        // we use binary search to just speed up the process, otherwise we can do a linear n*q search as well which would result in TLE though\n        vector<long long> pref (maxi+1, 0);\n        pref[0] = gcdCount[0];\n        for(int i = 1; i <= maxi; i++) pref[i] = pref[i-1] + gcdCount[i];\n\n        vector<int> ans;\n        for(auto q:queries)\n        {\n            int low = 1, high = maxi ; \n            int res ;\n            while(low <= high){\n                int mid = (low + high)/2;\n                if(pref[mid] > q){\n                    res = mid;\n                    high = mid - 1;\n                }\n                else\n                {\n                    low = mid + 1;\n                }   \n            }\n            ans.push_back(res);\n        }\n        return ans;   \n\n    }\n};\n```
['C++']