#3312

Sorted GCD Pair Queries

hard · premium · 22.4% accepted · 100 likes · top 2%

array · hash table · math · binary search · combinatorics · counting · number theory · prefix sum

Description

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

Let gcdPairs denote an array obtained by calculating the GCD of all possible pairs (nums[i], nums[j]), where 0 <= i < j < n, and then sorting these values in ascending order.

For each query queries[i], you need to find the element at index queries[i] in gcdPairs.

Return an integer array answer, where answer[i] is the value at gcdPairs[queries[i]] for each query.

The term gcd(a, b) denotes the greatest common divisor of a and b.

Solution