incremental count greatest common divisor and their factors
time: O(n sqrt(n)) or O(n log n) ?.   Thanks to ye15.\n\n\nfrom math import gcd, sqrt\nclass Solution:\n    def coutPairs(self, nums: List[int], k: int) -> int:
time: O(n sqrt(n)) or O(n log n) ?.   Thanks to ye15.\n\n```\nfrom math import gcd, sqrt\nclass Solution:\n    def coutPairs(self, nums: List[int], k: int) -> int:\n        factors = []\n        for i in range(1, k+1):\n            if k % i == 0:\n                factors.append(i)\n        # print("factors:", factors)\n                \n        ans = 0\n        gcd_freq = defaultdict(int)\n        for v in nums:\n            gc = gcd(v, k)\n            other = k // gc\n            if other in gcd_freq:\n                ans += gcd_freq[other]\n            \n            for f in factors:\n                if gc % f == 0:\n                    gcd_freq[f] += 1\n\n        # print(gcd_freq)\n        return ans\n```
['Python']