[Java/C++/Python] Easy and Concise with Explanation
Explanation\nCount all elements greatest common divisor with k.\nFor each pair (a, b) of divisors, check if a * b % k == 0\n\n\n# Complexity\nTime O(nlog100000 
# **Explanation**\nCount all elements greatest common divisor with `k`.\nFor each pair `(a, b)` of divisors, check if `a * b % k == 0`\n<br>\n\n# **Complexity**\nTime `O(nlog100000 + k * k)`\nSpace `O(k)`\nwhere `k` is the number of divisors of `k`.\n\n# **Value of K**\nprovided by @megurine\n83160 and 98280 have the biggest number of diviors, which is 128.\n83160 = 11*7*5*3*3*3*2*2*2\n98280 = 13*7*5*3*3*3*2*2*2\n\nprovided by @endlesscheng\nMaximal number of divisors of any n-digit number\nhttps://oeis.org/A066150\n<br>\n\n**Java**\nby @blackspinner\n```java\n    public long countPairs(int[] nums, int k) {\n        Map<Long, Long> cnt = new HashMap<>();\n        long res = 0L;\n        for (int x : nums) {\n            cnt.merge(BigInteger.valueOf(x).gcd(BigInteger.valueOf(k)).longValue(), 1L, Long::sum);\n        }\n        for (long x : cnt.keySet()) {\n            for (long y : cnt.keySet()) {\n                if (x <= y && x * y % k == 0L) {\n                    res += x < y ? cnt.get(x) * cnt.get(y) : cnt.get(x) * (cnt.get(x) - 1L) / 2L;\n                }\n            }\n        }\n        return res;\n    }\n```\n**C++**\nby @alexunxus\n```\nlong long coutPairs(vector<int>& nums, int k) {\n        unordered_map<int, int> mp;\n        for (int& nu: nums) {\n            mp[gcd(nu, k)]++;\n        }\n        long long res = 0;\n        for (auto& [a, c1]: mp) {\n            for (auto & [b, c2]: mp) {\n                if (a <= b && a*(long) b %k == 0) {\n                    res += a < b?(long)c1*c2:(long)c1*(c1-1)/2;\n                }\n            }\n        }\n        return res;    \n    }\n```\n**Python**\n```py\n    def coutPairs(self, A, k):\n        cnt = Counter(math.gcd(a, k) for a in A)\n        res = 0\n        for a in cnt:\n            for b in cnt:\n                if a <= b and a * b % k == 0:\n                    res += cnt[a] * cnt[b] if a < b else cnt[a] * (cnt[a] - 1) // 2\n        return res\n```\n
['C', 'Python', 'Java']