Python 3: TC O(n*log(k) + k^(2/log(log(k)))), SC O(k^(1/log(log(k)))): Group by GCD, Try All Pairs
Intuition\n\nThis is a pretty nasty problem because it requires you to know, or at least guess, that the divisor counting function grows slowly with k.\n\n## Ea
# Intuition\n\nThis is a pretty nasty problem because it requires you to know, or at least guess, that the divisor counting function grows slowly with `k`.\n\n## Easy Part: Numbers Divisible by k\n\nIf we have `D` numbers divisible by `k`, then\n* every pair of numbers, `D*(D-1)//2`, is also divisible by `k`\n* and every pair where one is divisible by `k`, and the other is not, their product is also divisible: `D*(N-D)`\n\n## Hard Part: Numbers Not Divisible by k\n\nSuppose we look at some number `n` where `n % k > 0`. `n` is not divisible.\n\nThen `n` is missing some of the factors required to be divisible by `k`. The factors it *does* have are `gcd(n, k)`. The factors it does not have are `k // gcd(n, k)`. This is because `gcd` has the minimum of the powers of each prime factor in both numbers\' prime factorizations.\n\nTherefore all numbers with a given value of `g == gcd(n, k)` are missing the same prime factors: `k//g`. Therefore if we found another bucket of numbers with `g\' == k//g` (`g, g\' < k` since these numbers are not divisible by `k`) then those numbers have the remaining factors we need, and thus all pairs of numbers where one is in `g` and the other has `g\'` will be divisible by `k`.\n\n**"Brute force" works here: we can iterate over all pairs of `g, g\'`.**\n\n## Complexity\n\nThe idea of iterating over all pairs of buckets might seem like it would give TLE.\n\nBut it turns out that\n* the number of buckets is the number of distinct divisors of `k`\n* this is the divisor counting function\n* the divisor counting function grows slowly\n  * it grows as `O(k^(1/log(log(k))))`\n  * the approximation is decent for large `k`, e.g. for `k=250` it predicts about 25 divisors at most, which is about right\n  * for `1e5` is predicts about 111 divisors, which is also about right (the real answer I think is about 130)\n\nAnd therefore we can afford to iterate over all of the bucket pairs.\n\n# Approach\n\nFirst I count the number of `nums` divisible by `k` by themeselves, and handle all pairs involving such numbers immediately.\n\nThen for the other numbers I get bucket counts by `g == gcd(n, k)` value.\n\nThen iterate over all pairs of buckets, `g1, g2`. If `g1*g2` is divisible by `k` then\n* if `g1 == g2` then it\'s the same bucket, any number in the bucket can be combined with any other value in the bucket; there are `f1 choose 2` pairs\n* otherwise they\'re different buckets so there are `f1*f2` pairs\n\n# Complexity\n- Time complexity: `O(n*log(k) + k^(2/log(log(k))))`\n  - the first part is from computing `gcd(n, k)` for every number, which takes `log(min(n, k))` operations\n  - the second part is from iterating over all pairs of buckets brute force\n  - there are `O(k^(1/log(log(k))))` distinct divisors of `k`. So squaring this is the number of pairs\n\n- Space complexity: `O(k^(1/log(log(k))))` because we have a bucket for every distinct divisor of `k`\n\nFor more on the asymptotics of the divisor counting function, [see here](https://resources.saylor.org/wwwresources/archived/site/wp-content/uploads/2012/06/MA111_Wikipedia_Divisor-Function_6.8.2012.pdf).\n\n# Code\n```python3 []\nclass Solution:\n    def countPairs(self, nums: List[int], k: int) -> int:\n        # if we have {D} and {N} where {D} is divis by k\n        #    then we have |D| choose 2 plus |D|*|N|\n\n        N = len(nums)\n        D = sum(n % k == 0 for n in nums)\n        ans = D*(D-1)//2 + D*(N-D)\n\n        if D == N: return ans\n\n        # how do we handle non-divis-by-k?\n\n        # after learning some more number theory from other comments, asymptotics of distinct divisors function\n\n        # if n is not a multiple of k, then gcd(n, k) < k\n        # and thus we\'re missing factors k // gcd(n, k)\n        # so every number with a given gcd(n, k) == g is missing the same factors k//g,\n        # any number in a bucket with gcd == k//g or a multiple of it will have the remaining factors we need\n\n        # how many gcds are there? the number of distinct divisors of `k`\n        # that function turns out to grow very slowly, O(k^eps) for eps < 0\n        # more realistic bound is O(k^(1/log(log(k)))) which is bizarre,\n        # see here: https://resources.saylor.org/wwwresources/archived/site/wp-content/uploads/2012/06/MA111_Wikipedia_Divisor-Function_6.8.2012.pdf\n        #\n        # so if we brute force all "gcd buckets" brute force we get complexity `O(n log(k))` for GCDs,\n        # then iterating over gcd buckets is `O(k^(2/log(log(k))))`. Weird. But true.\n\n        counts = Counter(gcd(n, k) for n in nums if n % k)\n        for (g1, f1), (g2, f2) in combinations_with_replacement(counts.items(), 2):\n            if (g1*g2) % k == 0:\n                if g1 == g2: ans += f1*(f1-1)//2\n                else: ans += f1*f2\n\n        return ans\n```
['Python3']