Answer queries about the sorted list of GCD values formed by all pairs in an array.
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.
For each query, determine the -th smallest GCD among all unordered pairs of elements in the array.
nums of positive integers.k in the sorted multiset of pair GCD values.i < j.k, output the k-th smallest value in the sorted list of all pair GCDs.1 <= nums.lengthnums[i] > 0n * (n - 1) / 2 unordered pairs total.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
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.