[Go] GCD count with detailed explanation
For this problem, we wish to find all pairs of numbers (a,b) such that a*b % k == 0.\nIt\'s clear that doing this for all pairs is too expensive, so we need to 
For this problem, we wish to find all pairs of numbers `(a,b)` such that `a*b % k == 0`.\nIt\'s clear that doing this for all pairs is too expensive, so we need to somehow group \nnumbers together.\n\nFirst, some background.\n\nAll numbers have a prime factorization. For example, `192 = 2*2*2*7*7`. \nFor prime numbers, the factor is simply itself times 1.\n\nThe greatest common denominator of two numbers, i.e. `gcd(a,b)` is the common\nprime factorizations of a and b. For example, given `a = 192 = 2*2*2*7*7` and \n`b = 21 = 3*7`, the GCD is `7`.\n\nWhen we take the GCD (`a,k`) of each element `a` in `nums`, we remove all\nprime factors from each element that are not in common with `k`. We know \nthat there aren\'t that many of these factors - in fact, we can find all factors \nthat evenly divide k in `O(sqrt(N))` time, so there are *at most* sqrt(N) factors.\n\nLet\'s take an example from one of the test cases:\n\n```\nnums = [8, 10, 2, 5, 9, 6, 3, 8, 2]\nk = 6\n```\n\nNow, `k = 6 = 3*2`. The only possible factors that divide k are `6, 3, 2, 1`, so\nthere can be at most 4 different numbers after doing `gcd(a,k)`:\n\n```\nnums = [8, 10, 2, 5, 9, 6, 3, 8, 2]\nfactors = [2*2*2, 2*5, 2, 5, 3*3, 3*2, 3, 2*2*2, 2]\nk = 2*3\ncommon_factors = [2, 2, 2, 1, 3, 6, 3, 2, 2]\n```\n\nNotice how few factors there are.\n\nNow comes the interesting part: since `gcd(a,k)` captures common prime factors\nbetween `a` and `k`, then any `gcd(a,k) * gcd(b,k)` where `a` and `b` contain\nall factors in `k` must be evenly divisible by `k`. If a factor exists e.g.\ntwice, it will just create a larger number still divisible by `k`.\n\nTherefore, `gcd(a,k)*gcd(b,k) % k = 0` if `(a * b) % k = 0`.\n\nThe final tricky part is when `a` == `b`. This can happen when e.g. `k` is a square\nand `a` is its root, or when `a` is equal to `k`. \n\nFor this case, the number of unique pairs is `n(n-1)/2`: there are `n` elements to \nchoose from in the first element, then `n-1`, hence `n*(n-1)`. Then divide by \nhalf to removeduplicates.\n\n# Solution\n\n```go\nfunc countPairs(nums []int, k int) int64 {\n\tgcd := func(a, b int) int {\n\t\tfor b != 0 {\n\t\t\ta, b = b, a%b\n\t\t}\n\t\treturn a\n\t}\n    \n\tn := int(math.Sqrt(float64(k)))\n\tgcds := make(map[int]int, n)\n\tfor _, num := range nums {\n\t\tgcds[gcd(num, k)]++\n\t}\n\n\tvar res int\n\tfor a, n1 := range gcds {\n\t\tfor b, n2 := range gcds {\n\t\t\tif a > b || (a*b)%k != 0 {\n\t\t\t\tcontinue\n\t\t\t}\n\t\t\tif a != b {\n\t\t\t\tres += n1 * n2\n\t\t\t} else { // a == b\n\t\t\t\tres += n1 * (n1 - 1) / 2\n\t\t\t}\n\t\t}\n\t}\n\treturn int64(res)\n}\n```
['Go']