[C++] Here's a sweet and short solution.
Intuition\n Describe your first thoughts on how to solve this problem. \nThe time complexity is bound to exceed in the bruteforce O(n^2) solution, so we need to
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe time complexity is bound to exceed in the bruteforce `O(n^2)` solution, so we need to come up with something better.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can achieve that with a bit of precomputational maths, taking the help of GCDs. \nThe code uses an unordered map (gcdCount) to keep track of the count of numbers that share the same GCD (highest common factor) value. It iterates through the nums vector and, for each element, calculates the GCD with the target value "k." It then checks the count of elements with a GCD that is a multiple of "k" and accumulates these counts.\n\n\n# Complexity\n- **Time complexity:** $$O(N*sqrt(k))$$ \n- - The outer loop iterates over the entire area, ie, N times.\n- - In each iteration, `gcd` function takes `O(log(min(num, k)))` time, and the inner loop takes `O(sqrt(k))` time because our map contains at max `2*sqrt(k)` factors of k, the latter taking more time, leading to overall $$O(N*sqrt(k))$$ time.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- **Space complexity:** $$O(sqrt(k))$$ \n- - The maximum number of factors any number `k` can have is `2*sqrt(k)`. \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\nThe code for this problem is fairly simple:\n```\nclass Solution {\npublic:\n    long long countPairs(vector<int>& nums, int k) {\n        unordered_map <int, int> gcdCount;\n        long long cnt = 0;\n        for (int num: nums) {\n            int hcf = gcd(num, k); //highest common factor (another name for gcd)\n            int required = k/hcf;\n            for (pair<int, int> p: gcdCount) {\n                if (p.first % required == 0) cnt += p.second;\n            }\n            gcdCount[hcf]++;\n        }\n        return cnt;\n    }\n};\n```
['Array', 'Math', 'Number Theory', 'C++']