gg [Beautiful Problem]
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 []\n#include <bits/stdc++.h>\n#define re return\n#define ff first\n#define ss second\n#define pb push_back\n#define gcd __gcd\n#define maxheap priority_queue<ll> // max heap\n#define minheap priority_queue<ll, vector<ll>, greater<ll>>\n#define pii pair<int, int>\n#define pll pair<ll, ll>\n#define lb *lower_bound\n#define up *upper_bound\n#define endl "\\n"\n#define all(x) (x).begin(), (x).end()\n#define allr(x) (x).rbegin(), (x).rend()\n#define INF LONG_LONG_MAX\n#define PI 3.141592653589793238462\n#define sz(x) ((ll)(x).size())\n#define rev(a) reverse(all(a))\nusing ll = long long;\nusing ull = unsigned long long;\nusing lld = long double;\n// Practice Till Death\n// Always Pass things by reference in dp\n// Always memoisation is not easy\n// Read Question twice\nusing namespace std;\n\nclass Solution {\npublic:\n    vector<int> gcdValues(vector<int>& nums, vector<long long>& q) {\n        ll val = 5*1e4 + 1;\n        vector<int> ans;\n        ll n = sz(nums);\n        vector<ll> f(val,0);\n        vector<ll> cnt(val,0);\n\n        for(auto it : nums)\n        f[it]++;\n\n        for(int i = 1; i < val; i++)\n        {\n            for(int j = i; j < val; j += i)\n            cnt[i] += f[j];\n\n            cnt[i] = ((cnt[i]) * (cnt[i] - 1))/2;\n        }\n\n        for(int i = val - 1; i >= 1; i--)\n        {\n            for(int j = 2*i; j < val; j += i)\n            cnt[i] -= cnt[j];\n        }\n\n        vector<pair<ll,ll>> g;\n\n        for(int i = 0; i < val; i++)\n        {\n            if(cnt[i])\n            g.pb({i,cnt[i]});\n        }\n\n        vector<ll> pref(g.size(),0);\n        pref[0] = g[0].ss;\n\n        for(int i = 1; i < sz(g); i++)\n        {\n            pref[i] = pref[i-1] + g[i].ss;\n        }\n\n        for(auto it : q)\n        {\n            ll ind = lower_bound(all(pref),it + 1) - pref.begin();\n            if(ind == pref.size())\n            ind = sz(pref) - 1;\n            ans.pb(g[ind].ff);\n        }\n\n        return ans;\n    }\n};\n```
['C++']