0 ms |  100% Beats  | unordered Map | C++
IntuitionApproachComplexity
Time complexity:

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

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

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

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

# Code
```cpp []
class Solution {
public:
    long long countPairs(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        long long cnt = 0;

        for (int num : nums) {
            int gcd1 = __gcd(num, k);
            for (auto [gcd2, f] : freq) {
                if ((1LL * gcd1 * gcd2) % k == 0) {
                    cnt += f;
                }
            }
            freq[gcd1]++;
        }
        return cnt;
    }
};

/*
        int cnt=0;
        int n=nums.size();

        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                if((nums[i]*nums[j]) % k == 0){
                    cnt++;
                }
            }
        }
        return cnt;
*/        
```
['C++']