Tap here to switch tabs
Problem
Submissions

Problem: Sorted GCD Pair Queries

Try to solve the Sorted GCD Pair Queries problem.

Statement

You are given an integer array nums of length n and an integer array queries.

Consider all pairs of indices (i, j) such that 0≤i<j<n0 \leq i < j < n. For each pair, compute the greatest common divisor of nums[i] and nums[j]. Collect all of these values into an array gcdPairs and sort it in ascending order.

For each query queries[i], find the value located at index queries[i] in the sorted gcdPairs array.

Return an array of integers containing the answer to each query in queries.

Constraints:

  • 2≤n==2 \leq n == nums.length ≤105\leq 10^5

  • 1≤1 \leq nums[i] ≤5imes104\leq 5 imes 10^4

  • 1≤1 \leq queries.length ≤105\leq 10^5

  • 0≤0 \leq queries[i] <nimes(n−1)2< \frac{n imes (n - 1)}{2}

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Sorted GCD Pair Queries

Try to solve the Sorted GCD Pair Queries problem.

Statement

You are given an integer array nums of length n and an integer array queries.

Consider all pairs of indices (i, j) such that 0≤i<j<n0 \leq i < j < n. For each pair, compute the greatest common divisor of nums[i] and nums[j]. Collect all of these values into an array gcdPairs and sort it in ascending order.

For each query queries[i], find the value located at index queries[i] in the sorted gcdPairs array.

Return an array of integers containing the answer to each query in queries.

Constraints:

  • 2≤n==2 \leq n == nums.length ≤105\leq 10^5

  • 1≤1 \leq nums[i] ≤5imes104\leq 5 imes 10^4

  • 1≤1 \leq queries.length ≤105\leq 10^5

  • 0≤0 \leq queries[i] <nimes(n−1)2< \frac{n imes (n - 1)}{2}