Sieve based solution Time O(N * log(max(K, arr[i]))), Space O(max(K, arr[i]))
\n# Code\n\nclass Solution {\npublic:\n    long long countPairs(vector<int>& nums, int k) {\n        ios_base::sync_with_stdio(0);\n        cin.tie(0);\n\n     
\n# Code\n```\nclass Solution {\npublic:\n    long long countPairs(vector<int>& nums, int k) {\n        ios_base::sync_with_stdio(0);\n        cin.tie(0);\n\n        const int N = nums.size();\n        const int M = max(*max_element(nums.begin(), nums.end()), k);\n        \n        int sieve[M + 1], freq[M + 1];\n\n        memset(freq, 0, sizeof(freq));\n        memset(sieve, 0, sizeof(sieve));\n\n        for(auto e: nums)\n        if(e <= M)\n        freq[e]++;\n\n        for(long long int i=1; i<=M; i++)\n        for(long long int j=i; j<=M; j+=i)\n        sieve[i] += freq[j];\n\n        long long int ans = 0;\n\n        for(auto e: nums) { \n            ans += sieve[k / __gcd(e, k)];\n            if((long long int) e * e % k == 0)\n            ans--;\n        }\n\n        return ans>>1;\n    }\n};\n```
['C++']