Easy solution to understand
IntuitionApproachComplexity
Time complexity:O(NlogK)

Space complexity:O(logK)
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:O(NlogK)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:O(logK)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
int GCD(int x, int y){
    if(x<y){
        return GCD(y,x);
    }
    return (y==0)?x:GCD(y,x%y);
}
    long long countPairs(vector<int>& nums, int k) {
        int n=nums.size();
        unordered_map<int,int>mp;
        long long count=0;
        for(int i=0;i<n;i++){
            int gcd1=GCD(nums[i],k);
            for(auto& it:mp){
                if(((long long)gcd1 * it.first) % k == 0 ){
                    count += it.second;
                }
            }
            mp[gcd1]++;
        }
        return count;
    }
};
```
['Array', 'Math', 'Number Theory', 'C++']