beat 100% of other solution
Code\ncpp []\nclass Solution {\npublic:\n    vector<int> gcdValues(vector<int>& a, vector<long long>& q) {\n        int mx=*max_element(a.begin(), a.end());\n  
# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> gcdValues(vector<int>& a, vector<long long>& q) {\n        int mx=*max_element(a.begin(), a.end());\n        vector<long long> dp(mx+9), frq(mx+9);\n        vector<int> ans;\n        for (auto it:a) \n            frq[it]++;\n        for (int i=1; i<=mx; i++) \n            for (int j=i+i; j<=mx; j+=i) frq[i]+=frq[j];\n        for (int i=mx; i; i--) {\n            dp[i]=frq[i]*(frq[i]-1)>>1;\n            for (int j=i+i; j<=mx; j+=i) \n                dp[i]-=dp[j];\n        }\n        for (int i=2; i<=mx; i++) dp[i]+=dp[i-1];\n        \n        for (auto it:q) {\n            int l=0, r=mx+1, mid;\n            while (l<r) {\n                mid=l+r>>1;\n                if (it+1 <= dp[mid]) r=mid;\n                else l=mid+1;\n            }\n            ans.push_back(r);\n        }\n        return ans;\n    }\n};\n```
['C++']