Answer Sorted Pair-GCD Position Queries
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Given a positive integer array `nums`, form one greatest common divisor for every pair of different positions `(i, j)` with `i < j`. Sort all those GCD values in ascending order to obtain the conceptual array `gcdPairs`.
For each zero-based index in `queries`, return the GCD value at that index of `gcdPairs`. Preserve the order of the queries in the returned array.
The greatest common divisor of two positive integers is the greatest positive integer dividing both of them.
```cpp
class Solution {
public:
vector<int> gcdValues(vector<int>& nums, vector<long long>& queries);
};
```
### Examples
**Example 1:**
```text
Input: nums = [6,10,15,9], queries = [5,0,3,1]
Output: [5,1,3,2]
Explanation: The six pair GCDs, sorted, are [1,2,3,3,3,5]. Read positions 5, 0, 3, and 1 in that order.
```
**Example 2:**
```text
Input: nums = [8,8,12], queries = [0,2,1,2]
Output: [4,8,4,8]
Explanation: The two different pairs containing 12 each have GCD 4, and the pair of 8s has GCD 8. Thus gcdPairs is [4,4,8].
```
### Constraints
- `2 <= nums.length <= 100000`.
- `1 <= nums[i] <= 50000`.
- `1 <= queries.length <= 100000`.
- Every query satisfies `0 <= queries[i] < n * (n - 1) / 2`, where `n = nums.length`.
### Clarifying Questions
- Are equal values at different positions distinct occurrences? Yes. Count each pair of positions separately.
- Are pairs ordered? No. The condition `i < j` includes each pair once and excludes pairing a position with itself.
- Can a query be repeated, or can queries arrive out of order? Yes to both.
- Are queries zero-based? Yes.
- What type must hold a query index? The original API uses `long long`; the number of pairs can exceed a 32-bit signed integer.
### What a Strong Answer Covers
- Preserves pair multiplicities and distinguishes positions even when values repeat.
- Answers the zero-based ranks in the original query order.
- Supports the full pair-count bound and input sizes without requiring quadratic storage.
```hint Count values before finding ranks
Count how many pairs have GCD exactly g. Pairs whose two values are divisible by g also include pairs with larger GCDs that are multiples of g; account for those before answering sorted-position queries.
```
Overview: Answer zero-based queries into the sorted GCDs of every pair of distinct array positions. Preserve duplicate pair values and query order, including repeated queries.