DP
Code\n\nclass Solution:\n    def countPairs(self, nums: List[int], k: int) -> int:\n        @cache\n        def fn(k):\n            res = 0\n            for i i
# Code\n```\nclass Solution:\n    def countPairs(self, nums: List[int], k: int) -> int:\n        @cache\n        def fn(k):\n            res = 0\n            for i in range(len(nums)):\n                if nums[i]%k==0: res += 1\n            return res\n        res = 0\n        for i in range(len(nums)):\n            res += fn(k//gcd(k, nums[i]))\n            if nums[i]%(k//gcd(k, nums[i]))==0: res-=1\n        return res//2\n```
['Python3']