Python (Simple Hashmap)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\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```python3 []\nclass Solution:\n    def countPairs(self, nums, k):\n        n, dict1 = len(nums), defaultdict(int)\n\n        for i in range(n):\n            dict1[math.gcd(nums[i],k)] += 1 \n\n        count1, count2 = 0, 0 \n\n        for a in dict1:\n            for b in dict1:\n                if a*b%k == 0:\n                    if a == b:\n                        count1 += dict1[a]*(dict1[a]-1)//2 \n                    else:\n                        count2 += dict1[a]*dict1[b]\n\n        return count1 + count2//2\n```
['Python3']