Answer queries about the sorted list of GCD values formed by all pairs in an array.
Sorted GCD Pair Queries
You are given an array of positive integers. Consider every pair of indices with , and compute the value .
Collect all these pair GCD values into one list, sort the list in nondecreasing order, and then answer multiple queries about it. For each query, return the value at the requested position in the sorted list.
Because the list of pair GCD values can be very large, an efficient solution is required.
Goal
For each query, determine the -th smallest GCD among all unordered pairs of elements in the array.
Input Format
- An integer array
numsof positive integers. - An array of queries, where each query asks for a 1-indexed position
kin the sorted multiset of pair GCD values.
Interpretation
- Each pair uses distinct indices:
i < j. - The same GCD value may appear many times, once for each pair producing it.
Output Format
- Return an array of answers.
- For each query
k, output thek-th smallest value in the sorted list of all pair GCDs.
Constraints
1 <= nums.lengthnums[i] > 0- There are
n * (n - 1) / 2unordered pairs total. - Query positions are valid for the total number of pair GCDs.
Note: Exact official constraints are not available from the input metadata, but the intended solution should avoid enumerating all pairs explicitly for large n.
Example 1
Input
nums = [2, 3, 4], queries = [1, 2, 3]
Output
[1, 2, 2]
Explanation
The pair GCDs are gcd(2,3)=1, gcd(2,4)=2, gcd(3,4)=1. Sorted list: [1, 1, 2]. Thus the 1st, 2nd, and 3rd values are 1, 1, and 2. If queries are 1-indexed over the sorted multiset, the answers are [1, 1, 2].
Example 2
Input
nums = [6, 10, 15], queries = [1, 2, 3]
Output
[1, 2, 5]
Explanation
Pair GCDs are gcd(6,10)=2, gcd(6,15)=3, gcd(10,15)=5. Sorted list: [2, 3, 5].
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.