C++ O(n * sqrt(k)) solution with GCD (with comments and explanation)
Basic strategy\n We process the numbers one by one traversing from left to right.\n At any index j, we\'re looking for all indices i (i < j) such that nums[i] *
## Basic strategy\n* We process the numbers one by one traversing from left to right.\n* At any index `j`, we\'re looking for all indices `i` (`i < j`) such that `nums[i] * nums[j] = 0 (mod k)`.\n  Let\'s write it as `x * a = 0 (mod k)` substituting `a` for `nums[j]` and `x` for (a possible) `nums[i]` for readability.\n  We\'re looking for (count of) all `x`s that satisfy the above and which we\'ve **already encountered before** in our traversal.\n\n## Some maths now\n* What are the solutions for the linear recurrence `a*x = b (mod k)` ?\nThere could be infinitely many solutions depending upon whether `gcd(a, k)` divides `b` or not.\nIn our case, `b` is `0`. So, there are infinitely many solutions.\n(But we\'re looking for only those that occur in our array before `a` in left to right traversal)\n* In general, when there are more than one solution, we express the set of all possible solutions as\n  `x = x_0 + n * r (mod k)` where\n  `x_0 = b / gcd(a, k)` \n  `r = k / gcd(a, k)`  -------------------------------------------------- **(1)**\n  and `0 <= n < gcd(a, k)`\n* In our case, `x_0 = 0` so, the above simplifies to\n  `x = n * r (mod k)` for `0 <= n < gcd(a, k)` ------------- **(2)**\n  This can be written as\n  `x = q*k + n*r` for some integer `q` ------------------------------ **(3)**\n  `x = q*r*gcd(a,k) + n*r` or\n  `x = r*(q*gcd(a,k) + n)` ------------------------------------------ **(4)**\n* From the above, we can see that `r` is a divisor of `k` (from (1)) and also that `r` is a divisor of `x`.\n  In fact, (3) tells us that any number divisible by `r` is a solution to our equation.\n  Why?\n  Well, let `x` be divisible by `r`. So we can write\n  `x = r * Q` for some integer `Q`\n  By Euclid\'s division lemma, any integer `Q` can be writen as\n  `Q = p*quot + rem` for any positive `p` such that `0 <= rem < p`.\n  If we use `gcd(a, k)` for `p`, we get\n  `x = r * Q = r * (gcd(a,k)*qout + rem)` where `0 <= rem < gcd(a,k)`\n  This is exactly the form of (4).\n\n## Back to the main problem\nCool, coming back to our problem, and armed with the maths we did before, we can calculate\n`r = k / gcd(nums[j], k)`\nand then count all `nums[i]` that we\'ve seen before  which are divisibly by `r`.\n\nSo, we\'d need to determine all divisors of `k` and the keep track of the count of all numbers we\'ve\nseen before in our traversal that are divisible by each of these divisors\nWe can keep these counts updated as we traverse.\n\n## Complexity\n* Time: For each number, we go over all divisors of `k`. A tight bound on the number of divisors can be had, but `sqrt(k)` is a good upper bound (since divisors occur in pairs). So time complexity is `O(n * sqrt(k))`. This could be considered amortized cost as the amortized `O(1)` cost of unordered_map access is should also be in there.\n* Space: `sqrt(k)` each for the divisors vector and the the unordered_map. So `O(sqrt(k))` in total.\n```\nclass Solution {\npublic:\n    long long coutPairs(vector<int>& nums, int k) {\n        using sum_type = long long;\n        \n        // divisor -> count of nums seen so far divisible by divisor\n        unordered_map<int,int> nums_divisible_by_divisor;\n        vector<int> divisors;\n        \n        // Populate the divisors of `k`\n        for(int i = 1; i <= k; i++) {\n            if(k % i == 0)\n                divisors.push_back(i);\n        }\n        \n        sum_type total = 0;\n        \n        for(auto const &num: nums) {\n            // Refer to the text outside of code, to get the significance of `r`\n            int r = k / gcd(num, k);\n            \n            // We do this to avoid adding elements in the hashmap while doing lookup.\n            // That might be convenient syntax wise, but we could end up adding\n            // quite a few useless values in the hashmap. It would not lead to\n            // incorrect results, but might trigger some rebalancing which is unnecessary.\n            if(auto it = nums_divisible_by_divisor.find(r); it != nums_divisible_by_divisor.end())\n                total += it->second;\n            \n            // This is where we update the divisor -> counts map for the incoming number `num`\n            // and maintain the "seen so far" invariant.\n            for(auto const &divisor : divisors) {\n                if(num % divisor == 0)\n                    nums_divisible_by_divisor[divisor]++;\n            }\n        }\n        \n        return total;\n    }\n};\n```
['C', 'C++']