Simple Solution with Math Proof and Estimation
Intuition\nThe first intuition is to replace each number with the greatest common divisor of this number with k, i.e. the number is replaced with some divisor o
# Intuition\nThe first intuition is to replace each number with the greatest common divisor of this number with `k`, i.e. the number is replaced with some divisor of `k`.\nThis can be done because `num1*num2` is divisible by `k` if and only if `gcd(num1,k)*gcd(num2,k)` is divisible by `k`. The proof is given at the end of the message.\nSince the number of divisors of a number is small, the number of different numbers in the sequence after the transformation can be significantly reduced.\nSince the number of divisors of `k` does not depend on the number of numbers in the sequence, the number of pairwise tests of the condition does not depend on the length of the sequence, but depends on the number of divisors of `k`.\nThe number of divisors of `k` increases more slowly than any power of the number ($$o(k^\\epsilon)$$ for all $$\\epsilon > 0$$ or $$O(k^{2/\\log \\log k})$$).\nThe number of steps of the Euclidean algorithm for calculating the greatest common divisor is no more than 5 times the number of digits in the decimal notation of the minimum number ($$5*\\log_{10} k $$).\n\nThe second consideration is that the divisors of `k` should be sorted in ascending order, and the condition should be checked for pairs of divisors by combining small divisors with large divisors.\n\n\n# Complexity\n- Time complexity:\n\n$$O(n*log_{10} k + k^{4/\\log \\log k})$$\n- Space complexity:\n\n$$O(k^{2/\\log \\log k})$$\n# Code\n```python3 []\nclass Solution:\n    def countPairs(self, nums: List[int], k: int) -> int:\n        map = Counter(math.gcd(num,k) for num in nums)\n        ans=0\n        if k in map:\n            count=map[k]\n            ans+=count*len(nums)-count*(count+1)//2\n            del map[k]\n        divisors=sorted(map.keys())\n        len_divisors = len(divisors)-1\n        for i, divisor in enumerate(divisors):\n            d = k//divisor\n            count= map[divisor]\n            if divisor % d==0:\n                ans+=count*(count-1)//2\n            for j in range(len_divisors,i,-1):\n                if divisors[j] < d: \n                    break\n                if divisors[j]%d==0:\n                    ans+=count*map[divisors[j]]\n        return ans    \n       \n\n        \n```
['Python3']