🚀Easy C Language Solution Using Suitable Array Concepts🚀 with Best Runtime
IntuitionThe goal is to determine the number of valid pairs (i, j) in the array nums such that the product of nums[i] and nums[j] is divisible by k. Instead of
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The goal is to determine the number of valid pairs (i, j) in the array nums such that the product of nums[i] and nums[j] is divisible by k. Instead of iterating over all pairs 𝑂(𝑛2), we optimize by focusing on the greatest common divisors (GCDs) of the numbers with respect to 𝑘. By precomputing frequencies of GCD values, we can efficiently count the pairs satisfying the divisibility condition.
# Approach
<!-- Describe your approach to solving the problem. -->
1. **GCD Calculation:**
For each number in nums, calculate 
gcd(𝑛𝑢𝑚𝑠[𝑖],𝑘), which captures the factors of 𝑘 that the number is compatible with.
Use a frequency array or hashmap to store the count of each GCD value.

2. **Count Valid Pairs:**
Iterate over all pairs of stored GCDs (𝑔1,𝑔2):If 𝑔1×𝑔2mod 𝑘=0 this pair of GCDs is valid for the divisibility condition.Add the respective counts of pairs from these GCD groups.

3. **Handle Edge Cases:**
Avoid duplicate counting by ensuring 𝑔2≥𝑔1 in the iteration.
Use combination logic 𝐶(𝑛,2)for pairs within the same GCD group.

4. **Efficiency:**
By precomputing GCDs and frequencies, and only checking divisor pairs, we significantly reduce the number of operations compared to a brute-force approach.
# Complexity
- Time complexity: **O(n.log(max(nums[i],k)) + d2)**
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

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

# Code
```c []
#include <stdlib.h>
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

long long countPairs(int* nums, int numsSize, int k) {
    long long count = 0;
    int* freq = (int*)calloc(k + 1, sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        int g = gcd(nums[i], k);
        freq[g]++;
    }
    for (int g1 = 1; g1 <= k; g1++) {
        if (freq[g1] == 0) continue;

        for (int g2 = g1; g2 <= k; g2++) {
            if (freq[g2] == 0) continue;
            if ((long long)g1 * g2 % k == 0) {
                if (g1 == g2) {
                    count += (long long)freq[g1] * (freq[g1] - 1) / 2;
                } else {
                    count += (long long)freq[g1] * freq[g2];
                }
            }
        }
    }
    free(freq);

    return count;
}

```
['C']