Java Soln With explanation
Idea ===> If we break into components let\'s say k = 425 = 100. And a = 128 and b = 50.\nThen 4 will divide 128 and 25 will divide 50. So what we have to do is 
Idea ===> If we break into components let\'s say k = 4*25 = 100. And a = 128 and b = 50.\nThen 4 will divide 128 and 25 will divide 50. So what we have to do is that we need to find gcd(a,k) and gcd(b,k) such that their multiple gcd(a,k)*gcd(b,k) is able to divide k.\n\nint x = gcd(a,k)\nint want = k/x\nkeep a map where we add all gcds\nif there is gcd which is able to get divide by want. add its count.\n```\nclass Solution {\n    public long countPairs(int[] nums, int k) {\n        int n = nums.length;\n        long count = 0L;\n        Map<Integer, Long> map = new HashMap<>();\n        \n        for(int i=0; i< n; i++){\n            int gd = gcd(nums[i],k);\n            int want = k/gd;\n            for(int p: map.keySet()){\n                if(p%want == 0){\n                    count += map.get(p);\n                }\n            }\n            map.put(gd,map.getOrDefault(gd,0L)+1L);\n        }\n        \n        return count;\n        \n    }\n    \n    public int gcd(int a, int b){\n        if(a>b){return gcd(b,a);}\n        if(a==0){return b;}\n        return gcd(a,b%a);\n    }\n}\n```
['Java']