Java Inclusion Exclusion + Binary Search Solution with comments
Code\njava []\nclass Solution {\n    public int[] gcdValues(int[] nums, long[] queries) {\n        int n = nums.length, maxEle = nums[0];\n        for(int i = 1
# Code\n```java []\nclass Solution {\n    public int[] gcdValues(int[] nums, long[] queries) {\n        int n = nums.length, maxEle = nums[0];\n        for(int i = 1; i < n; i++)  maxEle = Math.max(maxEle, nums[i]); //find the max elem\n\n        int freq[] = new int[maxEle + 1];\n        for(int i : nums)   freq[i]++; // get the frequenct of each elem\n\n        long gcdPairCount[] = new long[maxEle + 1]; //gcdPairCount[i] is how many pairs are having gcd val i\n        for(int cd = maxEle; cd > 0; cd--){     //choose a val \'x\' to find out how many pairs of gcd as that val \'x\'\n            long countOfEleWithDivisorCd = 0l;\n            for(int ele = cd; ele <= maxEle; ele += cd){ //find out how many elems have \'x\' as its divisor\n                countOfEleWithDivisorCd += freq[ele];\n            }\n            long countOfPairsWithCurrentCd = countOfEleWithDivisorCd * (countOfEleWithDivisorCd - 1) / 2; //make count into pair, this will give us pair who has common divisor as \'x\', \'x\' may or may not be gcd of those pairs\n\n            for(int ele = 2 * cd; ele <= maxEle; ele += cd){ //iterate from 2 * x and subract the pairs who has gcd as bigger number to get pairs who has gcd as \'x\'\n                countOfPairsWithCurrentCd -= gcdPairCount[ele];\n            }\n\n            gcdPairCount[cd] = countOfPairsWithCurrentCd; \n        }\n\n        long gcdPairCountPrefixSum[] = new long[maxEle + 1]; // gcdPairCountPrefixSum[i] denotes how many pair have gcd value <= i\n        for(int i = 1; i <= maxEle; i++){\n            gcdPairCountPrefixSum[i] = gcdPairCountPrefixSum[i - 1] + gcdPairCount[i]; \n        }\n\n        int result[] = new int[queries.length];\n        for(int i = 0; i < queries.length; i++){\n            result[i] = binarySearch(gcdPairCountPrefixSum, queries[i]); // do binary search to get the val of gcd who has queries[i]th elem\n        }\n        return result;\n    }\n    private int binarySearch(long arr[], long k){\n        int low = 0, high = arr.length - 1;\n        while(low <= high){\n            int mid = low + (high - low) / 2;\n            if(arr[mid] <= k)   low = mid + 1; //since k is index not elem we also consider \'=\'\n            else                high = mid - 1;\n        }\n        return low;\n    }\n}\n```
['Java']