题目描述

给你一个长度为 n 的整数数组 nums 和一个整数数组 queries。

gcdPairs 表示数组 nums 中所有满足 0 <= i < j < n 的数对 (nums[i], nums[j]) 的
最大公约数 升序 排列构成的数组。

对于每个查询 queries[i]，你需要找到 gcdPairs 中下标为 queries[i] 的元素。

请你返回一个整数数组 answer，其中 answer[i] 是 gcdPairs[queries[i]] 的值。

gcd(a, b) 表示 a 和 b 的 最大公约数。

样例

输入：nums = [2,3,4], queries = [0,2,2]

输出：[1,2,2]

解释：

gcdPairs = 
    gcd(nums[0], nums[1]),
    gcd(nums[0], nums[2]),
    gcd(nums[1], nums[2])
] = [1, 2, 1]

升序排序后得到 gcdPairs = [1, 1, 2]。

所以答案为 [
    gcdPairs[queries[0]],
    gcdPairs[queries[1]],
    gcdPairs[queries[2]]
] = [1, 2, 2]。

输入：nums = [4,4,2,1], queries = [5,3,1,0]

输出：[4,2,1,1]

解释：

gcdPairs 升序排序后得到 [1, 1, 1, 2, 2, 4]。

输入：nums = [2,2], queries = [0,0]

输出：[2,2]

解释：

gcdPairs = [2]。

限制

• 2 <= n == nums.length <= 10^5
• 1 <= nums[i] <= 5 * 10^4
• 1 <= queries.length <= 10^5
• 0 <= queries[i] < n * (n - 1) / 2

算法

(预处理，二分) $O(n + (U + q) \log U)$

1. 求出对于每个 $g$，有多少个数对的最大公约数为 $g$。
2. 朴素的方式是枚举每个数字的约数 $p$，得到每个约数 $p$ 所对应的数字个数 $c$，然后 $\frac{(c-1)c}{2}$ 就是数对的个数。更高效的做法是先统计每个数字的出现次数，然后可以通过枚举倍数的方式得到每个数字作为约数时，关联的数字个数。
3. 上述得到的数对个数会出现重复，例如当公约数为 $k$ 时，其 $k$ 的约数对应的数对被重复统计了，所以需要扣除。
4. 然后对 $g$ 数组求前缀和。
5. 对于每个询问，二分查找位置满足其前缀的公约数个数有 $q+1$ 个。

时间复杂度

• 假设最大的数字为 $U$，则预处理的时间复杂度为 $O(n + U \log U)$。
• 寻找答案的时间复杂度为 $O(q \log U)$。
• 故总时间复杂度为 $O(n + (U + q) \log U)$。

空间复杂度

• 需要 $O(U)$ 的额外空间存储预处理的数组。

C++ 代码

#define LL long long

class Solution {
public:
    vector<int> gcdValues(vector<int>& nums, vector<LL>& queries) {
        int m = 0;
        for (int x : nums)
            if (m < x)
                m = x;

        vector<int> h(m + 1, 0);
        for (int x : nums)
            ++h[x];

        vector<LL> g(m + 1, 0);
        for (int i = m; i >= 1; i--) {
            int c = 0;
            for (int j = i; j <= m; j += i)
                c += h[j];

            g[i] = (LL)(c - 1) * c / 2;
            for (int j = i + i; j <= m; j += i)
                g[i] -= g[j];
        }

        for (int i = 2; i <= m; i++)
            g[i] += g[i - 1];

        vector<int> ans;
        for (LL q : queries) {
            ++q;

            int l = 1, r = m;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (g[mid] < q) l = mid + 1;
                else r = mid;
            }

            ans.push_back(l);
        }

        return ans;
    }
};