Easy Java Solution 🔥 Beats 75% of Java Users .
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int gcd( int a , int b ){\n        while( b!=0 ){\n            int temp = a ; \n            a = b ; \n            b = temp % b ; \n        }\n        return a ; \n    }\n    public void fill( HashMap<Integer,Integer> map , int factor ){\n        for(int i : map.keySet() ){\n            if( factor % i == 0 ) {\n                map.put( i , map.get(i) + 1 ) ; \n            }\n        }\n    }\n    int inter = 0 ; \n    public long countPairs(int[] nums, int k) {\n        long rs = 0 ;\n        int n = nums.length ; \n        HashMap<Integer,Integer> map = new HashMap<>() ; \n        for(int i=2 ; i<=k/2 ; ++i){\n            if( k%i == 0 ){\n                map.put( i , 0 ) ; \n            }\n        }\n        int inter = 0 ; \n        for(int i=0 ; i<n ; ++i ){\n            if( nums[i] % k == 0  ){\n                rs += (n-1 -inter) ;\n                inter++; \n            }else {\n                int curr = gcd( nums[i] , k ) ;\n                if( curr == 1 ) continue ;  \n                rs += map.getOrDefault( k/curr , 0 )  ; \n                fill( map , curr ) ; \n            }\n            \n        }\n        return rs ; \n    }\n}\n```
['Java']