C++ Solution  || 100% Faster || Using GCD || With proper detailed comments , intution and approach
Intuition\n Describe your first thoughts on how to solve this problem. \nFirstly i thought of a brute force solution of N^2 where i check for each element and t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirstly i thought of a brute force solution of N^2 where i check for each element and then i observerd a pattern that if i take the gcd of a number with k and multiplying it with other number\'s gcd with k.\nIf it gives me value >=k then i can add it to my answer.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIt is quite simple and obvious approach.\nWe traverse from nums from ltor and for each i in nums we check if there exists someone with gcd of k/gcd(nums[i],k) if it does then add  to my answer the number of times such gcd exists.\nAnd after that i put the current gcd to my map.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->O(N*sqrt(k))\nAs the outer loop will traverse N times and inner loop will traverse the number of times factors of k.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(sqrt(k)) \nAs we are using an unordered map to store the factors of k.\n\n# Code\n```\nclass Solution {\npublic:\n    long long countPairs(vector<int>& nums, int k) {\n        unordered_map<int,int> mp;\n        long long ans = 0;\n        int n = nums.size();\n        for(int i=0;i<n;i++){\n            //gcd of current number\n            int curr = gcd(nums[i],k);\n            for(auto it : mp){\n                //checking if any gcd exists with value k/curr\n                if((1LL*curr*(it.first))%k == 0){\n            //if it does then adding to my ans number of such gcd\'s\n                    ans += it.second;\n                }\n            }\n            //finally adding it to my map\n            mp[gcd(nums[i],k)]++;\n        }\n        return ans;\n    }\n};\n```
['Array', 'Math', 'Number Theory', 'C++']