3312. 排序的最大公约数对查询

Hard

题目描述

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

设 gcdPairs 是一个数组，通过计算所有可能的配对 (nums[i], nums[j]) 的最大公约数得到，其中 0 <= i < j < n，然后将这些值按升序排序。

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

返回一个整数数组 answer，其中 answer[i] 是每个查询对应的 gcdPairs[queries[i]] 的值。

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

示例 1：

输入：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]

示例 2：

输入：nums = [4,4,2,1], queries = [5,3,1,0]
输出：[4,2,1,1]
解释：
gcdPairs 按升序排序是 [1, 1, 1, 2, 2, 4]

示例 3：

输入：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

提示：

尝试计算有 GCD 为 g 的对的数量
使用容斥原理

解题思路

这道题需要高效地计算所有数对的 GCD 并排序，然后回答查询。直接枚举所有数对会导致 O(n²) 的时间复杂度，对于大规模输入会超时。

核心思路： 使用容斥原理 + 二分查找的方法：

统计频率：首先统计每个数字在数组中出现的频次
计算倍数频次：对每个可能的 GCD 值 g，计算有多少个数字是 g 的倍数
容斥原理：如果有 cnt 个数字是 g 的倍数，那么这些数字构成的数对有 cnt*(cnt-1)/2 个，但这包含了 GCD 为 g 的倍数的情况，需要用容斥原理减去
前缀和：计算 GCD 值的前缀和，便于二分查找
二分查找：对每个查询，通过二分查找找到第 k 小的 GCD 值

算法步骤：

统计 nums 中每个数字的频次
从大到小遍历所有可能的 GCD 值 g（1 到最大值）
对每个 g，统计其倍数的个数，计算数对数量
使用容斥原理：减去更大 GCD 值的贡献
构建前缀和数组
对每个查询进行二分查找

时间复杂度为 O(M log M + Q log M)，其中 M 是数组中的最大值，Q 是查询数量。

代码实现

class Solution {
public:
    vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {
        int n = nums.size();
        int maxVal = *max_element(nums.begin(), nums.end());
        
        // 统计每个数字的频次
        vector<int> cnt(maxVal + 1, 0);
        for (int x : nums) {
            cnt[x]++;
        }
        
        // 统计每个数字的倍数个数
        vector<long long> multiples(maxVal + 1, 0);
        for (int g = 1; g <= maxVal; g++) {
            for (int k = g; k <= maxVal; k += g) {
                multiples[g] += cnt[k];
            }
        }
        
        // 计算每个GCD值的数对数量（使用容斥原理）
        vector<long long> gcdCount(maxVal + 1, 0);
        for (int g = maxVal; g >= 1; g--) {
            long long total = multiples[g];
            gcdCount[g] = total * (total - 1) / 2;
            
            // 减去更大GCD值的贡献
            for (int k = 2 * g; k <= maxVal; k += g) {
                gcdCount[g] -= gcdCount[k];
            }
        }
        
        // 构建前缀和
        vector<pair<int, long long>> gcdList;
        for (int g = 1; g <= maxVal; g++) {
            if (gcdCount[g] > 0) {
                gcdList.push_back({g, gcdCount[g]});
            }
        }
        
        vector<long long> prefix(gcdList.size() + 1, 0);
        for (int i = 0; i < gcdList.size(); i++) {
            prefix[i + 1] = prefix[i] + gcdList[i].second;
        }
        
        // 回答查询
        vector<int> result;
        for (long long q : queries) {
            int left = 0, right = gcdList.size();
            while (left < right) {
                int mid = (left + right) / 2;
                if (prefix[mid + 1] > q) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            result.push_back(gcdList[left].first);
        }
        
        return result;
    }
};

class Solution:
    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:
        n = len(nums)
        max_val = max(nums)
        
        # 统计每个数字的频次
        cnt = [0] * (max_val + 1)
        for x in nums:
            cnt[x] += 1
        
        # 统计每个数字的倍数个数
        multiples = [0] * (max_val + 1)
        for g in range(1, max_val + 1):
            for k in range(g, max_val + 1, g):
                multiples[g] += cnt[k]
        
        # 计算每个GCD值的数对数量（使用容斥原理）
        gcd_count = [0] * (max_val + 1)
        for g in range(max_val, 0, -1):
            total = multiples[g]
            gcd_count[g] = total * (total - 1) // 2
            
            # 减去更大GCD值的贡献
            for k in range(2 * g, max_val + 1, g):
                gcd_count[g] -= gcd_count[k]
        
        # 构建前缀和
        gcd_list = []
        for g in range(1, max_val + 1):
            if gcd_count[g] > 0:
                gcd_list.append((g, gcd_count[g]))
        
        prefix = [0] * (len(gcd_list) + 1)
        for i in range(len(gcd_list)):
            prefix[i + 1] = prefix[i] + gcd_list[i][1]
        
        # 回答查询
        result = []
        for q in queries:
            left, right = 0, len(gcd_list)
            while left < right:
                mid = (left + right) // 2
                if prefix[mid + 1] > q:
                    right = mid
                else:
                    left = mid + 1
            result.append(gcd_list[left][0])
        
        return result

public class Solution {
    public int[] GcdValues(int[] nums, long[] queries) {
        int n = nums.Length;
        int maxVal = nums.Max();
        
        // 统计每个数字的频次
        int[] cnt = new int[maxVal + 1];
        foreach (int x in nums) {
            cnt[x]++;
        }
        
        // 统计每个数字的倍数个数
        long[] multiples = new long[maxVal + 1];
        for (int g = 1; g <= maxVal; g++) {
            for (int k = g; k <= maxVal; k += g) {
                multiples[g] += cnt[k];
            }
        }
        
        // 计算每个GCD值的数对数量（使用容斥原理）
        long[] gcdCount = new long[maxVal + 1];
        for (int g = maxVal; g >= 1; g--) {
            long total = multiples[g];
            gcdCount[g] = total * (total - 1) / 2;
            
            // 减去更大GCD值的贡献
            for (int k = 2 * g; k <= maxVal; k += g) {
                gcdCount[g] -= gcdCount[k];
            }
        }
        
        // 构建前缀和
        List<(int gcd, long count)> gcdList = new List<(int, long)>();
        for (int g = 1; g <= maxVal; g++) {
            if (gcdCount[g] > 0) {
                gcdList.Add((g, gcdCount[g]));
            }
        }
        
        long[] prefix = new long[gcdList.Count + 1];
        for (int i = 0; i < gcdList.Count; i++) {
            prefix[i + 1] = prefix[i] + gcdList[i].count;
        }
        
        // 回答查询
        int[] result = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            long q = queries[i];
            int left = 0, right = gcdList.Count;
            while (left < right) {
                int mid = (left + right) / 2;
                if (prefix[mid + 1] > q) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            result[i] = gcdList[left].gcd;
        }
        
        return result;
    }
}

var gcdValues = function(nums, queries) {
    const n = nums.length;
    const maxVal = Math.max(...nums);
    
    // 统计每个数字的频次
    const cnt = new Array(maxVal + 1).fill(0);
    for (const x of nums) {
        cnt[x]++;
    }
    
    // 统计每个数字的倍数个数
    const multiples = new Array(maxVal + 1).fill(0);
    for (let g = 1; g <= maxVal; g++) {
        for (let k = g; k <= maxVal; k += g) {
            multiples[g] += cnt[k];
        }
    }
    
    // 计算每个GCD值的数对数量（使用容斥原理）
    const gcdCount = new Array(maxVal + 1).fill(0);
    for (let g = maxVal; g >= 1; g--) {
        const total = multiples[g];
        gcdCount[g] = Math.floor(total * (total - 1) / 2);
        
        // 减去更大GCD值的贡献
        for (let k = 2 * g; k <= maxVal; k += g) {
            gcdCount[g] -= gcdCount[k];
        }
    }
    
    // 构建前缀和
    const gcdList = [];
    for (let g = 1; g <= maxVal; g++) {
        if (gcdCount[g] > 0) {
            gcdList.push([g, gcdCount[g]]);
        }
    }
    
    const prefix = new Array(gcdList.length + 1).fill(0);
    for (let i = 0; i < gcdList.length; i++) {
        prefix[i + 1] = prefix[i] + gcdList[i][1];
    }
    
    // 回答查询
    const result = [];
    for (const q of queries) {
        let left = 0, right = gcdList.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (prefix[mid + 1] > q) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        result.push(gcdList[left][0]);
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	描述
时间复杂度	O(M log M + Q log K)，其中 M 是数组最大值，Q 是查询数量，K 是不同 GCD 值的数量
空间复杂度	O(M + K)，用于存储计数数组和前缀和数组

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析