Count number of pairs for all possible gcd
Intuition\nCount number of pairs for all possible gcd , and then binary search for every query\n\n# Approach\n\n\n\n# Complexity\n- Time complexity:\n Add your 
# Intuition\nCount number of pairs for all possible gcd , and then binary search for every query\n\n# Approach\n![Screenshot 2024-10-06 165346.png](https://assets.leetcode.com/users/images/10c34cef-0cab-46cc-b57e-f8f84b1eb101_1728213901.656282.png)\n\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 bs(long arr[],long x) {\n        int s = 1;\n        int e = arr.length-1;\n        int ans = arr.length-1;\n        while(s<=e) {\n            int mid = (s+e)/2;\n            if(arr[mid]>=x) {\n                e = mid-1;\n                ans = mid;\n            } else {\n               s = mid+1;\n            } \n        }\n        return ans;\n    }\n    public int[] gcdValues(int[] nums, long[] queries) {\n        HashMap<Integer,Integer> map = new HashMap<>();\n        int max = 0;\n        for(int i=0; i<nums.length; i++) {\n            map.put(nums[i],map.getOrDefault(nums[i],0)+1);\n            max = Math.max(nums[i],max);\n        }\n        long b[] = new long[max+1];\n        for(int i=max; i>=1; i--) {\n            int curr = i;\n            long count = 0;\n            while(curr<=max) {\n                count = count + map.getOrDefault(curr,0);   \n                curr = curr + i;\n            }\n            if(count>0) {\n                b[i] = ((long)(count)*(count-1))/2;\n            }\n        }\n        for(int i=max; i>=1; i--) {\n            for(int j = i*2; j<=max; j=j+i) {\n                b[i] = b[i]-b[j];\n            }\n        }\n        long total = 0;\n        for(int i=0; i<b.length; i++) {\n            total = total + b[i];\n            b[i] = total;\n            System.out.print(b[i]+" ");\n        }\n        int ans[] = new int[queries.length];\n        for(int i=0; i<queries.length; i++) {\n            ans[i] = bs(b,queries[i]+1);\n            // if(b[ans[i]]!=queries[i]+1) {\n            //     ans[i]--;\n            // }\n        }\n        return ans;\n    }\n}\n```
['Java']