Math solution|| Brute Force || Optimised
Intuition
If pairs product is divisible by k increment count
Approach
Initialise count to 0
Start iterating for pair(i,j)
i from 0 to n-1 and j from i+1 to n
if
# Intuition
- If pairs product is divisible by k increment count
# Approach
- Initialise count to 0
- Start iterating for pair`(i,j)`
- `i` from 0 to n-1 and `j` from `i+1` to n
- if their product is divisible by `k` increment count
<!-- Describe your approach to solving the problem. -->

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

- Space complexity:$$O(1)$$
<!-- Add your space complexity here, e.g.  -->
# Code
```java []
class Solution {
    public long countPairs(int[] nums, int k) {
        long count=0;
        int n = nums.length;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if((nums[i] * nums[j])%k==0)count++;
            }
        }
        return count;
    }
}
```

# Intuition
- If `gcd(num[i], k) * gcd(num[j], k)` is divisible by `k` , `num[i] * num[j]` should also be divisible.
<!-- Describe your first thoughts on how to solve this problem. -->
# Approach
-  Use a hash map to store the frequency of each unique GCD value encountered so far.
# Complexity
- Time complexity:  $$O(n * m)$$, where `n` is the length of the array and `m` is the number of unique GCD values encountered
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:$$O(n)$$
<!-- Add your space complexity here, e.g.  -->
# Code
```java []
class Solution {
    public int gcd(int a,int b){
        if(b==0)return a;
        return gcd(b,a%b);
    }
    public long countPairs(int[] nums, int k) {
        long count=0;
        int n = nums.length;
        HashMap<Integer,Integer> hm = new HashMap<>();
        for(int i:nums){
            int gcdnum= gcd(i,k);
            for(Map.Entry<Integer,Integer> entry : hm.entrySet()){
                if(((long)gcdnum*entry.getKey())%k==0){
                    count+=entry.getValue();
                }
            }
            hm.put(gcdnum,hm.getOrDefault(gcdnum,0)+1);
        }
        return count;
    }
}
```
['Array', 'Hash Table', 'Math', 'Number Theory', 'Java']