Python solution (beats 97%)
\nclass Solution:\n    def countPairs(self, nums: List[int], k: int) -> int:\n        d = collections.defaultdict(int)\n        for i,n in enumerate(nums):\n   
```\nclass Solution:\n    def countPairs(self, nums: List[int], k: int) -> int:\n        d = collections.defaultdict(int)\n        for i,n in enumerate(nums):\n            d[math.gcd(n,k)] += 1\n        ans = 0\n        for a in d:\n            for b in d:\n                if b >= a and a*b%k == 0:\n                    if a != b:\n                        ans += d[a]*d[b]\n                    else:\n                        ans += d[a]*(d[a]-1)//2\n        return ans\n```
['Hash Table', 'Math', 'Python']