Small and intutive
-- Add your space complexity here, e.g. O(n) -->\n\n# Code\ncpp []\n#define ll long long\nclass Solution {\npublic:\n    vector<int> gcdValues(vector<int>& nums
-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\n#define ll long long\nclass Solution {\npublic:\n    vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {\n        ll n=size(nums), mx=*max_element(begin(nums), end(nums));\n        vector<ll> cntdiv(mx+1), cntgcd(mx+1);\n        for(int i:nums){\n            for(int j=1; j*j<=i; j++){\n                if(i%j==0){\n                    cntdiv[j]++;\n                    if(i/j!=j)cntdiv[i/j]++;\n                }\n            }\n        }\n        for(int i=mx; i>=1; i--){\n            cntgcd[i]=(cntdiv[i]*(cntdiv[i]-1))/2;\n            for(int j=2*i; j<=mx; j+=i)cntgcd[i]-=cntgcd[j];\n        }\n        vector<ll> pfx(mx+1);\n        pfx[0]=cntgcd[0];\n        for(int i=1; i<=mx; i++)pfx[i]=pfx[i-1]+cntgcd[i];\n        vector<int> ans;\n        for(ll i:queries){\n            int j=upper_bound(begin(pfx), end(pfx), i)-begin(pfx);\n            ans.push_back(j);\n        }\n        return ans;\n    }\n};\n```
['C++']