[Java Solution] When I did not know what GCD is
I didn\'t know what GCD was and didn\'t know the formular, all I was think is, assume k = a * b and a <=b, if I find all num in the nums array that\'s divisible
I didn\'t know what GCD was and didn\'t know the formular, all I was think is, assume k = a * b and a <=b, if I find all num in the nums array that\'s divisible to a in SetA and all num that\'s divisible to b in SetB, then I have a pair when I selete 1 element in setA and 1 element in SetB. Then the number of total pairs is size of setA * size of setB - number of duplicate counts\n```\nclass Solution {\n    public long coutPairs(int[] nums, int k) {\n        long n = (long) nums.length;\n        if (k==1) {\n            return (n*(n-1))/2;\n        }\n        \n        long ret = 0;\n        Map<Integer, Integer> map = new LinkedHashMap<>();\n\t\t// when k = 12, this map is like:\n\t\t// 1:12\n\t\t// 2:6\n\t\t// 3:4\n        for(int i=1; i<=k/2; i++) {\n            if(k % i == 0) {\n                int temp = k/i;\n                map.put(i, temp);\n            }\n        }\n        for(int a: map.keySet()) {\n            int b = map.get(a); // k = a * b and a <= b\n\t\t\tHashSet<Integer> setA = new HashSet<>();\n            HashSet<Integer> setB = new HashSet<>();\n\t\t\t// save all num[i] that\'s divisible to a in setA\n\t\t\t// save all num[i] that\'s divisible to b in setB\n\t\t\t// then if I select 1 element from setA and 1 element from setB I got a pair that multiplication is divisible to k\n            for(int i=0; i<nums.length; i++) {\n                if(nums[i] % a == 0) {\n                    setA.add(i);\n                } \n                if(nums[i] % b == 0) {\n                    setB.add(i);\n\t\t\t\t\t// marking this number to -1 so that next round, I don\'t need to count it again\n                    nums[i] = -1;\n                }\n            }\n            if(a == 1) {\n                long sizeB = (long) setB.size();\n\t\t\t\t// - (sizeB * (sizeB-1))/2 remove duplicate counts\n                ret += sizeB * (n -1) - (sizeB * (sizeB -1))/2;\n            } else {\n                HashSet<Integer> set = new HashSet<>();\n                for(int x: setA) set.add(x);\n                for(int x: setB) set.add(x);\n                long sizeA = (long) setA.size();\n                long sizeB = (long) setB.size();\n\t\t\t\t// overlap is the number of common num in setA and setB\n                long overlap = sizeA + sizeB - (long) set.size();\n\t\t\t\t// - overlay removes the scenario where we selected same element from setA and setB\n\t\t\t\t// - (overlap * (overlap-1))/2 remove duplicate counts\n                ret += sizeA * sizeB - overlap - (overlap * (overlap-1))/2;\n            }\n        }\n        return ret;\n    }\n}\n```
['Java']