class Solution {
public:
vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {
}
};
3312. 查询排序后的最大公约数
给你一个长度为 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 的 最大公约数 。
示例 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 <= 1051 <= nums[i] <= 5 * 1041 <= queries.length <= 1050 <= queries[i] < n * (n - 1) / 2原站题解
golang 解法, 执行用时: 116 ms, 内存消耗: 9.8 MB, 提交时间: 2024-10-09 22:07:29
func gcdValues(nums []int, queries []int64) []int {
mx := slices.Max(nums)
cntX := make([]int, mx+1)
for _, x := range nums {
cntX[x]++
}
cntGcd := make([]int, mx+1)
for i := mx; i > 0; i-- {
c := 0
for j := i; j <= mx; j += i {
c += cntX[j]
cntGcd[i] -= cntGcd[j] // gcd 是 2i,3i,4i,... 的数对不能统计进来
}
cntGcd[i] += c * (c - 1) / 2 // c 个数选 2 个，组成 c*(c-1)/2 个数对
}
for i := 2; i <= mx; i++ {
cntGcd[i] += cntGcd[i-1] // 原地求前缀和
}
ans := make([]int, len(queries))
for i, q := range queries {
ans[i] = sort.SearchInts(cntGcd, int(q)+1)
}
return ans
}
java 解法, 执行用时: 23 ms, 内存消耗: 63.4 MB, 提交时间: 2024-10-09 22:07:15
class Solution {
public int[] gcdValues(int[] nums, long[] queries) {
int mx = 0;
for (int x : nums) {
mx = Math.max(mx, x);
}
int[] cntX = new int[mx + 1];
for (int x : nums) {
cntX[x]++;
}
long[] cntGcd = new long[mx + 1];
for (int i = mx; i > 0; i--) {
int c = 0;
for (int j = i; j <= mx; j += i) {
c += cntX[j];
cntGcd[i] -= cntGcd[j]; // gcd 是 2i,3i,4i,... 的数对不能统计进来
}
cntGcd[i] += (long) c * (c - 1) / 2; // c 个数选 2 个，组成 c*(c-1)/2 个数对
}
for (int i = 2; i <= mx; i++) {
cntGcd[i] += cntGcd[i - 1]; // 原地求前缀和
}
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
ans[i] = upperBound(cntGcd, queries[i]);
}
return ans;
}
private int upperBound(long[] nums, long target) {
int left = -1, right = nums.length; // 开区间 (left, right)
while (left + 1 < right) { // 区间不为空
// 循环不变量：
// nums[left] <= target
// nums[right] > target
int mid = (left + right) >>> 1;
if (nums[mid] > target) {
right = mid; // 二分范围缩小到 (left, mid)
} else {
left = mid; // 二分范围缩小到 (mid, right)
}
}
return right;
}
}
cpp 解法, 执行用时: 169 ms, 内存消耗: 118.7 MB, 提交时间: 2024-10-09 22:07:02
class Solution {
public:
vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {
int mx = ranges::max(nums);
vector<int> cnt_x(mx + 1);
for (int x : nums) {
cnt_x[x]++;
}
vector<long long> cnt_gcd(mx + 1);
for (int i = mx; i > 0; i--) {
int c = 0;
for (int j = i; j <= mx; j += i) {
c += cnt_x[j];
cnt_gcd[i] -= cnt_gcd[j]; // gcd 是 2i,3i,4i,... 的数对不能统计进来
}
cnt_gcd[i] += (long long) c * (c - 1) / 2; // c 个数选 2 个，组成 c*(c-1)/2 个数对
}
partial_sum(cnt_gcd.begin(), cnt_gcd.end(), cnt_gcd.begin()); // 原地求前缀和
vector<int> ans(queries.size());
for (int i = 0; i < queries.size(); i++) {
ans[i] = ranges::upper_bound(cnt_gcd, queries[i]) - cnt_gcd.begin();
}
return ans;
}
};
python3 解法, 执行用时: 458 ms, 内存消耗: 36.6 MB, 提交时间: 2024-10-09 22:06:47
class Solution:
def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:
mx = max(nums)
cnt_x = [0] * (mx + 1)
for x in nums:
cnt_x[x] += 1
cnt_gcd = [0] * (mx + 1)
for i in range(mx, 0, -1):
c = 0
for j in range(i, mx + 1, i):
c += cnt_x[j]
cnt_gcd[i] -= cnt_gcd[j] # gcd 是 2i,3i,4i,... 的数对不能统计进来
cnt_gcd[i] += c * (c - 1) // 2 # c 个数选 2 个，组成 c*(c-1)/2 个数对
s = list(accumulate(cnt_gcd)) # 前缀和
return [bisect_right(s, q) for q in queries]