[Python] Clear solution with explanation
Idea\nThe problem asks us to find all pair (a, b) that a * b could be dividable by k. When traverse the array and we see a, we could calculate gcd(a, k), and re
Idea\nThe problem asks us to find all pair **(a, b)** that **a * b** could be dividable by **k**. When traverse the array and we see **a**, we could calculate **gcd(a, k)**, and record remaining **r = k // gcd(a, k)**. When we see **b**, we check all previous **r** to see if **b** could be devided by **r**. If yes, we found a pair.\n\n```\nclass Solution:\n    def coutPairs(self, nums: List[int], k: int) -> int:\n        def gcd(a, b):\n            if b > a:\n                return gcd(b, a)\n            if a % b == 0:\n                return b\n            else:\n                return gcd(b, a % b)\n        \n        res = 0\n        div = 0\n        n = len(nums)\n\n        # use cnt to record num of remaining of k//gcd(a, k)\n        cnt = defaultdict(int)\n        for num in nums:\n            # special handling for number that could be divied by k directly\n            # it could be paired with any other element.\n            # But it\'s possible that there are more than one such number, \n            # we use div to count number and substract it to avoid duplicate count\n            if num % k == 0:\n                res += n - 1 - div\n                div += 1\n            else:\n                # for each remaing of r from previous element, we check if r is dividable by num\n                # if yes, we found pairs\n                for key in cnt.keys():\n                    if num % key == 0:\n                        res += cnt[key]\n\n                # add r for current num\n                g = gcd(num, k)\n                cnt[k//g] += 1\n        return res\n```
[]