Simple Mathematical Solution in Python beats 91.15%
Intuition\n Describe your first thoughts on how to solve this problem. \nConsider two numbers a and b and divisor k:\nConsider the division operation as (a * b)
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nConsider two numbers **a** and **b** and divisor **k**:\nConsider the division operation as $$(a * b) / k$$\nSo the division happens in 3 cases:\n\n**Case 1:** \nIf either a or b is divisible by k, then the product of these two numbers are divisible by k\n\n**Case 2:**\nIf both the number a and b are both divisible by k, then the product of these two numbers are divisible by k\n\n**Case 3:**\nIf both the numbers are not divisible by k, but the product of these numbers is divisible by k\n\nSo the solution below consider these three cases and solves the problem.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**Example:** $$nums = [3,1,2,2,2,1,3]$$ and $$k = 2$$\n\n**STEP 1:**\nCreate a map of the structure:\n****map = { key: ( [divisible_list], [non_divisible_list] ) }****\n\n**STEP 2:**\nTraverse the array, add key as the number and based on the divisibility populate the respective list with the indexes which are divisible by k and which are not divisible by k.\n\nNow after performing Step 1 and Step 2 your map looks like:\n*map = {3: ([0, 6], [ ]), 1: ([ ], [1, 5]), 2: ([2, 4], [3])}*\n\nIn above example for key 2, we can see that the indexes 2 and 4 are divisible by k=2 but index 3 is not divisible by k\nso it represented in the map as:\n\n*key = 2, divisible_list = [2, 4] and non_divisible_list = [3]*\n\n**STEP 3:**\nCount the number of pair that are divisible by k\n\nNow *Case 1: either a or b is divisible by k*\nTo calculate that, \n*(count of divisible elements) * (count of non divisible elements)* \nwill gives us the Case 1, pair count\n\nNext, *Case 2: If both the number a and b are both divisible by k*\nTo calculate that,\n$$(n * (n - 1)) / 2$$ where n is *count of divisible elements*\n\n\nNext, *Case 3: both the numbers are not divisible by k, but the product of these numbers is divisible by k*\nTo calculate the count here, you need to create the pair of using the numbers in non divisible list and then checking them whether they are divisible by k or not.\n\n\n# Complexity\n- Time complexity: $$O(n*y/2)$$ where n is the number of keys and y is count of number not divisible by k\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n * (x + y))$$ where n is number of keys and x in count of numbers divisible by k and y is the  count of numbers not divisible by k\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n<br>\n\n![image.png](https://assets.leetcode.com/users/images/d71975b1-be88-49c0-8bc7-3aadfe31c2fc_1687878100.4933174.png)\n\n<br>\n\n# Code\n```\nclass Solution:\n    def countPairs(self, nums: List[int], k: int) -> int:\n        map = {}\n        n = len(nums)\n\n        for i in range(n):\n            num = nums[i]\n\n            divisible = -1\n            non_divisible = -1\n\n            if i % k == 0:\n                divisible = i\n            else:\n                non_divisible = i\n\n            if num in map:\n                divisible_list = map[num][0]\n                non_divisible_list = map[num][1]\n                \n                if divisible >= 0:\n                    divisible_list.append(divisible)\n                \n                if non_divisible >= 0:\n                    non_divisible_list.append(non_divisible)\n            else:\n                divisible_list = []\n                non_divisible_list = []\n\n                if divisible >= 0:\n                    divisible_list.append(divisible)\n                \n                if non_divisible >= 0:\n                    non_divisible_list.append(non_divisible)\n\n                map[num] = (divisible_list, non_divisible_list)\n        \n        print(map)\n\n        count = 0\n\n        for key in map:\n            divisible_count = len(map[key][0])\n            non_divisible_count = len(map[key][1])\n            non_divisible_list = map[key][1]\n\n            # Case 2\n            count += (divisible_count * (divisible_count - 1)) // 2\n            # Case 1\n            count += (divisible_count * non_divisible_count)\n\n            # Case 3\n            for i in range(non_divisible_count):\n                for j in range(i + 1, non_divisible_count):\n                    a = non_divisible_list[i]\n                    b = non_divisible_list[j]\n\n                    if (a * b) % k == 0:\n                        count += 1\n        \n        return count\n```\n\n![image.png](https://assets.leetcode.com/users/images/8ec4fa12-15fa-4870-9e7b-a7dfaa3d017b_1687879921.00696.png)\n
['Python3']