solution using exculsion principal, and prefix sum
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```cpp []\nclass Solution {\npublic:\n    using ll = long long;\n    vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {\n        int n = nums.size();\n        int mx = *max_element(nums.begin(), nums.end());\n        vector<ll> freq(mx + 1), cnt(mx + 1);\n        for(auto it: nums) freq[it] ++ ;\n\n        for(int i=1; i<=mx; i++){\n            for(int j=i; j<=mx; j+=i){\n                cnt[i] += freq[j];\n            }\n            cnt[i] = (cnt[i]*(cnt[i]-1)/2); //for pair choosing\n        }\n        //exclusion principle\n        for(int i=mx; i>=1; i--){\n            for(int j=2*i; j<=mx; j+=i){\n                cnt[i] -= cnt[j];\n            }\n        }\n\n        vector<ll> pref(mx+2, 0);\n        for(int i=0; i<mx+1; i++) pref[i+1] = pref[i] + cnt[i];\n\n        vector<int> ans;\n        for(auto it: queries){\n            int ub = lower_bound(pref.begin(), pref.end(), it+1) - (pref.begin());\n            ans.push_back(ub-1);\n        }\n        return ans;\n    }\n};\n```
['C++']