sorted-gcd-pair-queries.cpp

// Time:  O(rlogr + qlogr), r = max(nums)
// Space: O(r)

// number theory, freq table, prefix sum, binary search
class Solution {
public:
    vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {
        unordered_map<int, int> cnt1;
        for (const auto& x : nums) {
            ++cnt1[x];
        }
        vector<int64_t> cnt2(ranges::max(nums) + 1);
        for (int g = size(cnt2) - 1; g >= 1; --g) {
            int64_t c = 0;
            for (int ng = g; ng < size(cnt2); ng += g) {
                c += cnt1[ng];
            }
            cnt2[g] = c * (c - 1) / 2;
            for (int ng = g + g; ng < size(cnt2); ng += g) {
                cnt2[g] -= cnt2[ng];
            }
        }
        vector<int64_t> prefix(size(cnt2) + 1);
        for (int i = 0; i < size(prefix) - 1; ++i) {
            prefix[i + 1] += prefix[i] + cnt2[i];
        }
        vector<int> result(size(queries));
        for (int i = 0; i < size(queries); ++i) {
            result[i] = distance(cbegin(prefix), upper_bound(cbegin(prefix), cend(prefix), queries[i])) - 1;
        }
        return result;
    }
};