Easy to understand solution
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\n    int lowerBound(long pref[] , long q){\n        int l=0,r=pref.length-1;\n        int ansIdx = -1 ; \n\n        while(l <= r){\n            int mid = l + (r-l) / 2 ; \n            if(pref[mid] >= q){\n                ansIdx = mid ; \n                r = mid - 1 ; \n            }\n            else l = mid + 1 ; \n        }\n        return ansIdx ; \n    }\n    public int[] gcdValues(int[] nums, long[] queries) {\n         int max = Integer.MIN_VALUE ; \n         for(int x : nums) max = Math.max(max , x) ; \n         int[] divCnt = new int[max + 1] ; \n\n         for(int i : nums){\n            for(int j=1;j*j<=i ;j++){\n                if(i % j == 0){\n                    divCnt[j]++ ; \n                    if(i/j != j) divCnt[i/j]++;\n                }\n            }\n         }\n\n         long[] gcdPairCnt = new long[max + 1] ; \n         long[] commonPart = new long[max + 1] ; \n         for(int i=max;i>=1;i--){\n            if(divCnt[i] < 2) continue ; \n            gcdPairCnt[i] = (long)divCnt[i] * (divCnt[i] - 1) / 2 - commonPart[i] ; \n            for(int j=1;j*j<=i ;j++){\n                if(i % j == 0){\n                    commonPart[j] += gcdPairCnt[i] ;  \n                    if(i/j != j) commonPart[i/j] += gcdPairCnt[i] ;\n                }\n            }\n         }\n\n         long pref[] = new long[max + 1] ; \n         for(int i=1;i<=max;i++) pref[i] = pref[i-1] + gcdPairCnt[i] ; \n\n         int ans[] = new int[queries.length] ; \n         for(int i=0;i<ans.length;i++) {\n            ans[i] = lowerBound(pref , queries[i]+1) ; \n         }\n\n         return ans ; \n    }\n}\n```
['Java']