Using map and gcd. Beats 100%.
Intuition\nThink of gcd. Calculate gcd and store the values in map.\n\nlike if gcd(k.nums[i]) = x;\nthen mp[x]++\n\noperate on this gcd for solution\n\n# Approa
# Intuition\nThink of gcd. Calculate gcd and store the values in map.\n\nlike if gcd(k.nums[i]) = x;\nthen mp[x]++\n\noperate on this gcd for solution\n\n# Approach\n\napproach is quite simple. calculate gcds and store in map.\n\nthen iterate through the map and for values k/value gcd \nmultiply the current frequency with k/value and its multiples frequency.\n\nif value == k/value the count should be increased by (freq-1)(freq) \n\nnot /2 because we are guiding ourselves through twice the possible ans.\n\nnow add half the values in the final answer because while doind \nk/value we actually added the results twice that is also intuitively satisfying.\n\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long countPairs(vector<int>& nums, int k) {\n\n        ios::sync_with_stdio(false);\n        cin.tie(nullptr);\n        cout.tie(nullptr);\n        \nlong long count = 0;\nunordered_map <int,int> mp;\nlong long x = 0;\nfor(auto it : nums){\n    if(it%k != 0 ){\n        mp[gcd(it,k)]++;\n    }\n    else{\nx++;\n    }\n}\n\n\ncount += x * nums.size() - (x*(x+1))/2;\n\nlong long y = 0;\nfor(auto it: mp){\n\n    int z  = k/it.first;\n    int zz = z;\n\n    while(zz < k){\n        if(mp.find(zz)!=mp.end()){\n        if(zz == it.first){\n            \n            y+= ((mp[zz]-1)*(mp[zz]));\n            \n        }\n       else y += mp[zz]*it.second;\n       }\n        zz+=z;\n    }\n\n}\n\n\n\n\ncount += y/2;\n\n\n\nreturn count;\n\n\n\n\n\n\n    }\n};               \n```
['C++']