[Python] O(Nsqrt(K)) Easy understand solution
Firstly, generate all divisors of k.\n Secondly, for each index i in nums, count the number of index j hold: \n    * j < i\n\t nums[j] MOD k/GCD(k, nums[i]) == 
* Firstly, generate all divisors of k.\n* Secondly, for each index `i` in `nums`, count the number of index `j` hold: \n    * `j < i`\n\t* `nums[j] MOD k/GCD(k, nums[i]) == 0`\n*  Obviously, `k/GCD(k, nums[i])` is a divisor of k. Therefore, we just need a counter to maintain the number of elements on the left divisible for each divisor of k.\n* Complexity: \n\t* Time: O(N * sqrt(K))\n\t* Space: O(sqrt(K))\n\n```\nclass Solution:\n    def coutPairs(self, nums: List[int], k: int) -> int:\n        N, output = len(nums), 0\n        divisors = []\n        counter = Counter()\n        \n        for i in range(1, k + 1):\n            if k % i == 0:\n                divisors.append(i)\n        \n        for i in range(0, N):\n            remainder = k // math.gcd(k, nums[i])\n            output += counter[remainder]\n            for divisor in divisors:\n                if nums[i] % divisor == 0:\n                    counter[divisor] += 1\n            \n        return output\n```
[]