GCD approach in C++
```\n// (n1n2)%k==0 can be implied in the same way [gcd(n1,k)gcd(n2,k)]%k==0, we do so because we only \n// require the prime factors of the numbers.\nclass Sol
```\n// (n1*n2)%k==0 can be implied in the same way [gcd(n1,k)*gcd(n2,k)]%k==0, we do so because we only \n// require the prime factors of the numbers.\nclass Solution {\npublic:\n    long long countPairs(vector<int>& nums, int k) {\n        unordered_map<long, long> mp;\n        long  long ans = 0;\n        for(int i=0;i<nums.size();i++){\n            int gcd1= __gcd(nums[i],k);\n            int gcd2= k/gcd1;\n            if(gcd2==1) ans+=i;\n            else{\n                for( auto it: mp){\n                    if(it.first % gcd2 == 0) ans+=it.second;\n                }\n            }\n            mp[gcd1]++;\n        }\n        \n        return ans;\n    }\n};
[]