Count Array Pairs Divisible by K
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(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++']