Easy to understand, beats 100%
Upvote would be appreciatedSolution ExplainedYou, like I, might have noticed that with smaller numbers it seems that every product that can be divided by k, one
***Upvote would be appreciated***\n# Solution Explained\nYou, like I, might have noticed that with smaller numbers it seems that every product that can be divided by k, one of the operands can also be divided by k,\n```\nk = 3 pair = (12, 11)\n12 * 11 = 132\n132 % 3 = 0 // is divisible by k\n12 % 3 = 0 // one of operands also is\n```\nThis isnt always the case though for example\n\n```\nk = 12 pair = (15, 32)\n15 * 32 = 480 \n480 % 12 = 0 // can be divided by k\n```\nNeither 15 or 32 can be divided by K, but there is a pattern.\n`15`\'s Greatest Common Denominator with `12` is `3`,\n`32`\'s Greatest Common Denominator with `12` is `4`.\n`4x3 % 12 = 0`\n\nBasically, if the product of two numbers GCD with k is divisible by k, then those two numbers are divisible by k, this works for every number.\n\n# Solution Implementation\nWe start by creating a HashMap, this will store `(GCD, frequency)`\n\nWe then iterate through every element of nums, we find the GCD between nums[i] and k using the Euclidean Algorithm. We add this value to the HashMap as the key, and if its already present (which it will be for almost all elements) we increment the value.\nWe also add the GCD\'s to a hashSet.\n\nWe then convert the set into an array, `denoms`\nAfter this it\'s sort of similiar to a basic 2sum solution.\nWe use a nested for loop(since there will always be very few unique GCD this wont affect the runtime much)\nIn the first for loop check if `denoms[i] * denoms[i] % k == 0`,\nThis checks if the current GCD multiplied by itself is divisble by k,\nfor example `6 * 6 % 12`, if it is we use the Sum Of All formula `x(x+1) / 2` with the value mapped to 6 in the HashMap `-1`, we subtract 1 as we dont want to include a pair with the same two elements. We add this value to the total.\nIn the inner for loop we check if GCD, `d` multiplied by a different GCD `m` is divisble by `k`, if so we multiply the HashMap value mapped to d and the HashMap value mapped to m, and add this to our total.\n\nThis is repeated until the outer loop has looped through every number in `denoms`\nThe result is then returned.\n\n\n# Code\n```java []\nclass Solution {\n    public long countPairs(int[] nums, int k) {\n        long total = 0;\n        HashMap<Integer, Integer> map = new HashMap<>();\n        Set<Integer> set = new HashSet<>();\n        for(int i = 0; i < nums.length; i++){\n            int d = hcd(nums[i], k);\n            map.put(d, map.getOrDefault(d, 0)+1);\n            set.add(d);\n        }\n        int[] denoms = set.stream().mapToInt(Integer :: intValue).toArray();\n        for(int i = 0; i < denoms.length; i++){\n            int d = denoms[i];\n            total+=((long) d * d % k == 0) ? sumOf(map.get(d)-1) : 0; \n            for(int j = i+1; j < denoms.length; j++){\n                int m = denoms[j];\n                total+= ((long)d*m)%k==0 ? (long) map.get(d) * map.get(m) : 0;\n            }\n        }\n        return total;\n    }\n    public int hcd(int a, int b){\n        while(b != 0){\n            int temp = a % b;\n            a = b;\n            b = temp;\n        }\n        return a;\n    }\n    public long sumOf(int x){\n        return (long) x*(x + 1) / 2;\n    }\n}\n```
['Hash Table', 'Math', 'Java']