[c++]
Intuition\n Describe your first thoughts on how to solve this problem. \nwe need a way to get count of each gcd, and then use binary search.\n\n1 count of all f
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nwe need a way to get count of each gcd, and then use binary search.\n\n1 count of all factor\n2 count of all gcd\n3 prefixsum of count of gcd\n4 binary search for each q\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 []\ntypedef long long ll;\nclass Solution {\npublic:\n    vector<int> gcdValues(vector<int>& nums, vector<long long>& qs) {\n        int n = nums.size();\n        sort(nums.begin(), nums.end());\n        int b = nums.back();\n        vector<ll> cnt(b + 1, 0);\n        for (auto v : nums) cnt[v]++;\n        for (int i = 1; i <= b; i++)\n        {\n            for (int j = i + i; j <= b; j+= i)\n            {\n                cnt[i] += cnt[j];\n            }\n            if (cnt[i] == 0) continue;\n            cnt[i] = (cnt[i] - 1) * cnt[i] / 2;\n        }\n        //cout << "a" << endl;\n        for (int i =  b - 1; i >= 1; i--)\n        {\n            for (int j = i + i; j <= b; j += i)\n            {\n                cnt[i] -= cnt[j];\n            }\n        }\n        //cout << 1 << endl;\n\n        vector<ll> prefix;\n        vector<int> vs;\n        for (int i = 1; i <= b; i++)\n        {\n            if (cnt[i] == 0) continue;\n            prefix.push_back(cnt[i]);\n            vs.push_back(i);\n        }\n\n        ll cur = 0;\n        for (int i = 0; i < prefix.size(); i++)\n        {\n            cur = prefix[i] + cur;\n            prefix[i] = cur;\n        }\n        //cout << 2 << endl;\n\n        vector<int> ans;\n        for (auto q : qs)\n        {\n            auto iter = upper_bound(prefix.begin(), prefix.end(), q);\n            int i = iter - prefix.begin();\n            ans.push_back(vs[i]);\n        }\n        return ans;\n    }\n};\n```
['C++']