| comments | difficulty | edit_url | tags | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
true |
Hard |
|
You are given an integer array nums of length n and an integer array queries.
Let gcdPairs denote an array obtained by calculating the GCD of all possible pairs (nums[i], nums[j]), where 0 <= i < j < n, and then sorting these values in ascending order.
For each query queries[i], you need to find the element at index queries[i] in gcdPairs.
Return an integer array answer, where answer[i] is the value at gcdPairs[queries[i]] for each query.
The term gcd(a, b) denotes the greatest common divisor of a and b.
Example 1:
Input: nums = [2,3,4], queries = [0,2,2]
Output: [1,2,2]
Explanation:
gcdPairs = [gcd(nums[0], nums[1]), gcd(nums[0], nums[2]), gcd(nums[1], nums[2])] = [1, 2, 1].
After sorting in ascending order, gcdPairs = [1, 1, 2].
So, the answer is [gcdPairs[queries[0]], gcdPairs[queries[1]], gcdPairs[queries[2]]] = [1, 2, 2].
Example 2:
Input: nums = [4,4,2,1], queries = [5,3,1,0]
Output: [4,2,1,1]
Explanation:
gcdPairs sorted in ascending order is [1, 1, 1, 2, 2, 4].
Example 3:
Input: nums = [2,2], queries = [0,0]
Output: [2,2]
Explanation:
gcdPairs = [2].
Constraints:
2 <= n == nums.length <= 1051 <= nums[i] <= 5 * 1041 <= queries.length <= 1050 <= queries[i] < n * (n - 1) / 2
We can preprocess to obtain the occurrence count of the greatest common divisor (GCD) of all pairs in the array
Let
- Calculate the occurrence count
$v$ of multiples of$i$ in the array$\textit{nums}$ . Then, the number of pairs formed by any two elements from these multiples must have a GCD that is a multiple of$i$ , i.e.,$\textit{cntG}[i]$ needs to be increased by$v \times (v - 1) / 2$ ; - We need to exclude pairs whose GCD is a multiple of
$i$ and greater than$i$ . Therefore, for multiples$j$ of$i$ , we need to subtract$\textit{cntG}[j]$ .
The above steps require us to traverse
Finally, we calculate the prefix sum of the array
The time complexity is
class Solution:
def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:
mx = max(nums)
cnt = Counter(nums)
cnt_g = [0] * (mx + 1)
for i in range(mx, 0, -1):
v = 0
for j in range(i, mx + 1, i):
v += cnt[j]
cnt_g[i] -= cnt_g[j]
cnt_g[i] += v * (v - 1) // 2
s = list(accumulate(cnt_g))
return [bisect_right(s, q) for q in queries]class Solution {
public int[] gcdValues(int[] nums, long[] queries) {
int mx = Arrays.stream(nums).max().getAsInt();
int[] cnt = new int[mx + 1];
long[] cntG = new long[mx + 1];
for (int x : nums) {
++cnt[x];
}
for (int i = mx; i > 0; --i) {
int v = 0;
for (int j = i; j <= mx; j += i) {
v += cnt[j];
cntG[i] -= cntG[j];
}
cntG[i] += 1L * v * (v - 1) / 2;
}
for (int i = 2; i <= mx; ++i) {
cntG[i] += cntG[i - 1];
}
int m = queries.length;
int[] ans = new int[m];
for (int i = 0; i < m; ++i) {
ans[i] = search(cntG, queries[i]);
}
return ans;
}
private int search(long[] nums, long x) {
int n = nums.length;
int l = 0, r = n;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] > x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
}class Solution {
public:
vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {
int mx = ranges::max(nums);
vector<int> cnt(mx + 1);
vector<long long> cntG(mx + 1);
for (int x : nums) {
++cnt[x];
}
for (int i = mx; i; --i) {
long long v = 0;
for (int j = i; j <= mx; j += i) {
v += cnt[j];
cntG[i] -= cntG[j];
}
cntG[i] += 1LL * v * (v - 1) / 2;
}
for (int i = 2; i <= mx; ++i) {
cntG[i] += cntG[i - 1];
}
vector<int> ans;
for (auto&& q : queries) {
ans.push_back(upper_bound(cntG.begin(), cntG.end(), q) - cntG.begin());
}
return ans;
}
};func gcdValues(nums []int, queries []int64) (ans []int) {
mx := slices.Max(nums)
cnt := make([]int, mx+1)
cntG := make([]int, mx+1)
for _, x := range nums {
cnt[x]++
}
for i := mx; i > 0; i-- {
var v int
for j := i; j <= mx; j += i {
v += cnt[j]
cntG[i] -= cntG[j]
}
cntG[i] += v * (v - 1) / 2
}
for i := 2; i <= mx; i++ {
cntG[i] += cntG[i-1]
}
for _, q := range queries {
ans = append(ans, sort.SearchInts(cntG, int(q)+1))
}
return
}