C solution (not C++)
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition\n<!-- I tried to solve it in O(n^2) complexity but now it is better-->\n\n# Approach\n<!-- GCD with basic math -->\n\n# Complexity\n- Time complexity:\n<!-- O(N+K^2) -->\n\n- Space complexity:\n<!-- O(K) -->\n\n# Code\n```c []\nint gcd(int a, int b) {\n    while (b) {\n        int temp = b;\n        b = a % b;\n        a = temp;\n    }\n    return a;\n}\n\nlong long countPairs(int* nums, int numsSize, int k) {\n    int* gcdFreq = (int*)calloc(k + 1, sizeof(int)); \n    long long result = 0;\n\n    for (int i = 0; i < numsSize; i++) {\n        int g = gcd(nums[i], k);\n        gcdFreq[g]++;\n    }\n\n    for (int i = 1; i <= k; i++) {\n        if (gcdFreq[i] == 0) continue;\n\n        for (int j = i; j <= k; j++) {\n            if ((long long)i * j % k == 0) {\n                if (i == j) {\n                    result += (long long)gcdFreq[i] * (gcdFreq[i] - 1) / 2;\n                } else {\n                    result += (long long)gcdFreq[i] * gcdFreq[j];\n                }\n            }\n        }\n    }\n\n    free(gcdFreq);\n    return result;\n}\n```
['C']