C++ | Divisors Counting and Binary Search | O(n * sqrt(MaxElement)) | Easy to understand
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nCount Divisors for Each Element:\nWe can first find the count how many el
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n**Count Divisors for Each Element:**\nWe can first find the count how many elements in the array nums are divisible by each number g (from 1 to the maximum element in v, maxx) and lets store them in cntDivisors .\nFor each element x in nums, we check its divisors (by iterating up to sqrt(x)). For each divisor i, both i and x / i are valid divisors. We increment the divisor count for both.\n\n**Count GCD Pairs:**\nThe array gcdCount[g] will store how many pairs in the array nums have GCD equal to g.\nFor each g starting from maxx and going down to 1, we calculate the number of pairs whose GCD is exactly g. This is done using:\nThe formula cntDivisors[g] * (cntDivisors[g] - 1) / 2, which gives the number of ways to choose two elements with GCD g.\n**// Now, Removing duplicate countings...**\nThen, we subtract the pairs that have a GCD of any multiple of g (to ensure only pairs with GCD exactly equal to g are counted). \nThis is done using the loop for (int mult = 2 * g; mult <= maxx; mult += g).\n\n**Prefix Sum Array:**\nWe create a prefix sum array pref where pref[g] stores the cumulative sum of all gcdCount[g] for g from 1 to g. This helps in efficiently answering the queries.\npref[g] will give the total number of pairs whose GCD is less than or equal to g.\n\n**Answering Queries:**\nFor each query q, which represents a rank, we need to find the smallest g such that the number of GCD pairs less than or equal to g is greater than q.\nWe use binary search on the pref array to find this value. The binary search helps efficiently find the answer without explicitly sorting or storing all the GCD pairs.\n\n# Complexity\n- Time complexity:\nO(n\u221Am + m log m + q log m) where m = MaxElement\n\n- Space complexity:\nO(MaxElement)\n\n# Code\n```cpp []\nclass Solution{\npublic:\n    vector<int> gcdValues(vector<int>& v, vector<long long>& q){\n        int n = v.size();\n        int maxx = *max_element(v.begin(), v.end());\n        vector<int> cntDivisors(maxx + 1, 0);\n        for(auto x : v){\n            for(int i = 1; i * i <= x; i++){\n                if(x % i == 0){\n                    cntDivisors[i]++;\n                    if(i != x / i){\n                        cntDivisors[x / i]++;\n                    }\n                }\n            }\n        }\n        vector<long long int> gcdCount(maxx + 1, 0);\n        for(int g = maxx; g >= 1; g--){\n            long long int count = cntDivisors[g];\n            gcdCount[g] = 1ll * count *(count - 1) / 2;\n            for(int mult = 2 * g; mult <= maxx; mult += g){\n                gcdCount[g] -= gcdCount[mult];\n            }\n        }\n        \n        vector<long long int> pref(maxx + 1, 0);\n        for(int g = 1; g <= maxx; g++){\n            pref[g] = pref[g - 1] + gcdCount[g];\n        }\n        vector<int> ans;\n        for(auto q : q){\n            long long int left = 1, right = maxx, answer = -1;\n            while(left <= right){\n                long long int mid =(left + right) / 2;\n                if(pref[mid] > q){\n                    answer = mid;\n                    right = mid - 1;\n                } else{\n                    left = mid + 1;\n                }\n            }\n            ans.push_back(answer);\n        }\n\n        return ans;\n    }\n};\n```
['Math', 'Binary Search', 'Prefix Sum', 'C++']