beautiful concept of gcd(a,k) * gcd(b,k) % k = 0 || easy to understand
nums[i]nums[j] is divisible by k than we can write as :-\ngcd(nums[i],k)gcd(nums[j],k) % k = 0\ngcd(a,b) \nif(b==0)\nreturn a;\nreturn gcd(b,a%b);\n\n\nclass So
nums[i]*nums[j] is divisible by k than we can write as :-\ngcd(nums[i],k)*gcd(nums[j],k) % k = 0\ngcd(a,b) \nif(b==0)\nreturn a;\nreturn gcd(b,a%b);\n\n```\nclass Solution {\n    public long countPairs(int[] nums, int k) {\n       HashMap<Integer,Long> map = new HashMap<>();\n       long ans = 0L;\n       for(int i=0;i<nums.length;i++){\n           int gcd = gcd(nums[i],k);\n           for(Map.Entry<Integer,Long> e : map.entrySet()){\n               long num = (long)e.getKey()*(long)gcd;\n               if(num%(long)k==0L)\n                   ans+=e.getValue();\n           }\n           map.put(gcd,map.getOrDefault(gcd,0L)+1L);\n       }\n        return ans;\n    }\n    public int gcd(int a,int b){\n        if(b==0)\n            return a;\n        return gcd(b,a%b);\n    }\n}\n\n```
['Math', 'Java']