JAVA SOLUTION: GCD AND DIVISORS SUM (N * sqrt(K))
X * Y divisble by K. If we know the value of X  and K then we can get minimum Y from K / gcd(X, K).\nExample: [1, 2, 3, 4, 5]`` andK = 2\n* If we select 0 index
```X * Y divisble by K```. If we know the value of ```X```  and ```K``` then we can get minimum ```Y``` from ```K / gcd(X, K)```.\nExample: ```[1, 2, 3, 4, 5]`` and ```K = 2```\n* If we select 0 index number from the array then X = 1 and K = 2 then minimum Y = 2. Now we need to know how many numbers from index 1 to 4 (2, 3, 4, 5) which has divisor Y = 2.  There are 2 numbers (2 , 4) have divisors 2. So add 2 to the answer.\n\n* If we select 1 index number from the array then X = 2 and K = 2 then minimum Y = 1. Now we need to know how many number from index 2 to 4(3, 4, 5) which has divisor Y = 1. There are 3 numers (3, 4, 5) have divisors 1. So add 3 to the answer.\n\n* If we select 2 index number from the array then X = 3 and K = 2 then minimum Y = 2. Now we need to know how many number from index 3 to 4 (4, 5) which has divisor Y = 2. There is only 1 number(4) has divisors 2. So add 1 to the answer.\n\n* If we select 3 index number from the array then X = 4 and K = 2 then minimum Y = 1. Now we need to know how many number from index 4 to 4 (5) which has divisor Y = 1. There is only 1 number(5) has divisors 1. So add 1 to the answer.\n\nTotal: 2 + 3 + 1 + 1 = 7\n\nTo get the count of divisors, we update frequency array for the divisor of every numbers.\n\ncode:\n```\npublic int gcd(int a, int b) {\n        int c;\n        while (b != 0) {\n            c = a % b;\n            a = b;\n            b = c;\n        }\n        return a;\n    }\n    \n    public long coutPairs(int[] nums, int k) {\n        int[] freq = new int[1000005];\n        int len = nums.length;\n        for (int i = 0; i < len; i++) {\n            for (int j = 1; j * j <= tmp; j++) {\n                if (nums[i] % j == 0) {\n                    freq[j]++;\n                    if (nums[i] / j != j) {\n                        freq[nums[i] / j]++;\n                    }\n                }\n            }\n        }\n        long ans = 0L;\n        for (int i = 0; i < len; i++) {\n            for (int j = 1; j * j <= nums[i]; j++) {\n                if (nums[i] % j == 0) {\n                    freq[j]--;\n                    if (nums[i] / j != j) {\n                        freq[nums[i] / j]--;\n                    }\n                }\n            }\n            int g = gcd(nums[i], k);\n            g = k / g;\n            ans += (long)freq[g];\n        }\n        return ans;\n    }\n\t```
['Java']