Inclusion-Exclusion DP
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:\nO(N* logN)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\nusing ll = long long;\npublic:\n    vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {\n        ll maxi = *max_element(begin(nums),end(nums));\n        vector <ll> f(maxi+1, 0);\n        vector <ll> ans(maxi+1,0);\n        for(auto num:nums) f[num]++;\n        for(ll i=1;i<=maxi;i++) {\n            ll ct = 0;\n            for(int j=i;j<=maxi;j+=i) {\n                ct += f[j];\n            }\n            ans[i]=(ct*(ct-1)/2);\n        }\n        for(ll i=maxi;i>=1;i--) {\n            for(ll j=i+i;j<=maxi;j+=i) {\n                ans[i]-=ans[j];\n            }\n        }\n        vector <ll> prefix(begin(ans),end(ans));\n        for(ll i=1;i<=maxi;i++) prefix[i]+=prefix[i-1];\n        vector <int> res;\n        for(auto q:queries) {\n            ll l=1;\n            ll r=maxi;\n            ll temp=maxi;\n            while(l<=r) {\n                ll mid=l+(r-l)/2;\n                if(prefix[mid]>=q+1) {\n                    temp=mid;\n                    r=mid-1;\n                }\n                else l=mid+1;\n            }\n            res.push_back(temp);\n        }\n        return res;\n    }\n};\n```
['Binary Search', 'Dynamic Programming', 'Prefix Sum', 'C++']