3312. Sorted GCD Pair Queries Hard

1/**
2 * [3312] Sorted GCD Pair Queries
3 *
4 * You are given an integer array nums of length n and an integer array queries.
5 * Let gcdPairs denote an array obtained by calculating the <span data-keyword="gcd-function">GCD</span> of all possible pairs (nums[i], nums[j]), where 0 <= i < j < n, and then sorting these values in ascending order.
6 * For each query queries[i], you need to find the element at index queries[i] in gcdPairs.
7 * Return an integer array answer, where answer[i] is the value at gcdPairs[queries[i]] for each query.
8 * The term gcd(a, b) denotes the greatest common divisor of a and b.
9 *  
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">nums = [2,3,4], queries = [0,2,2]</span>
13 * Output: <span class="example-io">[1,2,2]</span>
14 * Explanation:
15 * gcdPairs = [gcd(nums[0], nums[1]), gcd(nums[0], nums[2]), gcd(nums[1], nums[2])] = [1, 2, 1].
16 * After sorting in ascending order, gcdPairs = [1, 1, 2].
17 * So, the answer is [gcdPairs[queries[0]], gcdPairs[queries[1]], gcdPairs[queries[2]]] = [1, 2, 2].
18 * </div>
19 * <strong class="example">Example 2:
20 * <div class="example-block">
21 * Input: <span class="example-io">nums = [4,4,2,1], queries = [5,3,1,0]</span>
22 * Output: <span class="example-io">[4,2,1,1]</span>
23 * Explanation:
24 * gcdPairs sorted in ascending order is [1, 1, 1, 2, 2, 4].
25 * </div>
26 * <strong class="example">Example 3:
27 * <div class="example-block">
28 * Input: <span class="example-io">nums = [2,2], queries = [0,0]</span>
29 * Output: <span class="example-io">[2,2]</span>
30 * Explanation:
31 * gcdPairs = [2].
32 * </div>
33 *  
34 * Constraints:
35 * 
36 * 	2 <= n == nums.length <= 10^5
37 * 	1 <= nums[i] <= 5 * 10^4
38 * 	1 <= queries.length <= 10^5
39 * 	0 <= queries[i] < n * (n - 1) / 2
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/sorted-gcd-pair-queries/
45// discuss: https://leetcode.com/problems/sorted-gcd-pair-queries/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn gcd_values(nums: Vec<i32>, queries: Vec<i64>) -> Vec<i32> {
51        vec![]
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_3312() {
63    }
64}
65