Easy Solution
IntuitionApproachEdge Cases
All elements are multiples of
k (e.g., k=1 or all numbers are 0 modulo k).Small 𝑛 or k (e.g., n=1 or k=1)Large
n (up to 100,000) — T
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nEdge Cases\nAll elements are multiples of \nk (e.g., k=1 or all numbers are 0 modulo k).Small \uD835\uDC5B or k (e.g., n=1 or k=1)Large \nn (up to 100,000) \u2014 The algorithm handles it efficiently with a complexity of \n\uD835\uDC42(\uD835\uDC5B\u22C5\uD835\uDC51)O(n\u22C5d).\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:Each GCD computation takes \n\uD835\uDC42(log(min(\uD835\uDC4E,\uD835\uDC4F)))O(log(min(a,b))).\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```javascript []\n/**\n * @param {number[]} nums\n * @param {number} k\n * @return {number}\n */\nvar countPairs = function(nums, k) {\n    const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);\n    const freq = new Map(); // Store the frequency of gcds of nums[i] and k\n    let count = 0;\n\n    for (const num of nums) {\n        const gcdA = gcd(num, k);\n        \n        // Count all previous numbers whose gcd with k pairs with gcdA\n        for (const [gcdB, f] of freq.entries()) {\n            if ((gcdA * gcdB) % k === 0) {\n                count += f;\n            }\n        }\n\n        // Update the frequency of the current gcd\n        freq.set(gcdA, (freq.get(gcdA) || 0) + 1);\n    }\n\n    return count;\n};\n\n```
['JavaScript']