Java || Beats 100% || simplest code
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[] gcdValues(int[] nums, long[] queries) {\n        int max=Arrays.stream(nums).max().orElse(0);\n        long div[]=new long[max+1];// div[in] stores how many nums are divisible by \'in\'.\n        for(int i:nums){\n            for(int j=1;j*j<=i;j++){\n                if(i%j==0){\n                    div[j]++;\n                    if(j!=i/j){\n                        div[i/j]++;\n                    }\n                }\n            }\n        }\n        long pairs[]=new long[max+1];\n        for(int i=max;i>0;i--){\n            pairs[i]=(div[i]*(div[i]-1))/2;//nC2\n            // remove additional pair counts\n            for(int j=2*i;j<=max;j+=i){\n                pairs[i]-=pairs[j];\n            }\n        }\n        long presum[]=new long[max+1];\n        for(int i=1;i<=max;i++){\n            presum[i]=presum[i-1]+pairs[i];\n        }\n        int n=queries.length;\n        int ans[]=new int[n];\n        for(int i=0;i<n;i++){\n            long que=queries[i]+1;\n            ans[i]=lowerbound(que,presum);\n        }\n        return ans;\n    }\n    public static int lowerbound(long que,long pre[]){\n        int l=0,r=pre.length-1;\n        int ans=-1;\n        while(l<=r){\n            int m=(l+r)/2;\n            if(pre[m]>=que){\n                r=m-1;\n                ans=m;\n            }else{\n                l=m+1;\n            }\n        }\n        return ans;\n    }\n}\n```
['Java']