Just like Two-Sum hashmap
It\'s just like two sum in that we were storing the remaining part if the target sum was 10 and we found 7 we were storing the 10-7 in hashmap so if we found 3 
**It\'s just like two sum in that we were storing the remaining part if the target sum was 10 and we found 7 we were storing the 10-7 in hashmap so if we found 3 we will return it\'s index from there same we need to find the product which is divisible by k so for example if we need to make a pair which is divisible by 10 so by far we have found 12 so the [gcd](https://byjus.com/maths/greatest-common-divisor/) of 12,10 will be 2 now what is the other counter we need to find it is 5 hence if we find 5\'s multiple or 5 we will add this pair to answer**\n`So the time complexity here won\'t be O(n^2) because a number can only have limited factors hence for 10^5 the max will be (10^5)^1/2 so at max the loop will iterate upto 100 - 200 (roughly) `\n```py\nclass Solution:\n    def countPairs(self, nums: List[int], k: int) -> int:\n        counter = Counter() #hashmap dicitionary of python\n        ans = 0\n        n = len(nums)\n        \n        for i in range(n):\n            x = math.gcd(k,nums[i]) #ex: 10 = k and we have nums[i] as 12 so gcd will be 2\n            want = k // x #what do we want from upper ex: we need 5\n            for num in counter:\n                if num % want == 0: #so if we find a number that is divisible by 5 then we can multiply it to 12 and make it a factor of 10 for ex we find 20 so it will be 240 which is divisible by 10 hence we will add it to answer\n                    ans += counter[num] #we are adding the freq as we can find no of numbers that have same factor\n            counter[x] += 1 #here we are increasing the freq of 2 so that if we find 5 next time we can add these to the answer\n        return ans\n```\n```java\npublic class Solution {\n    public int countPairs(int[] nums, int k) {\n        // Create a HashMap to count the occurrences of numbers\n        Map<Integer, Integer> counter = new HashMap<>();\n        int ans = 0;\n        int n = nums.length;\n\n        for (int i = 0; i < n; i++) {\n            int gcdResult = gcd(k, nums[i]); // Calculate the GCD of \'k\' and \'nums[i]\'\n            int desiredFactor = k / gcdResult; // Calculate the desired factor to form a pair with \'nums[i]\'\n\n            for (int num : counter.keySet()) {\n                if (num % desiredFactor == 0) {\n                    // If \'num\' is divisible by the desired factor, it can form pairs with \'nums[i]\'\n                    // Add the frequency of \'num\' to the answer\n                    ans += counter.get(num);\n                }\n            }\n\n            // Increase the count of \'gcdResult\' in the HashMap\n            counter.put(gcdResult, counter.getOrDefault(gcdResult, 0) + 1);\n        }\n\n        return ans;\n    }\n```\n
['Hash Table', 'Python', 'Java', 'Python3']