Leetcode 3312. Sorted GCD Pair Queries

문제

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.

길이가 n인 정수 배열 nums와 정수 배열 queries가 주어집니다.

gcdPairs는 가능한 모든 인덱스 쌍 (i, j)에 대해,
0 <= i < j < n을 만족하는 nums[i]와 nums[j]의 최대공약수를 계산한 뒤, 그 값들을 오름차순으로 정렬하여 만든 배열입니다.

각 쿼리 queries[i]에 대해 gcdPairs의 queries[i]번째 인덱스에 있는 원소를 찾아야 합니다.

각 i에 대해 answer[i]가 gcdPairs[queries[i]]의 값이 되도록 정수 배열 answer를 반환하세요.

gcd(a, b)는 a와 b의 최대공약수를 의미합니다.

---

예시

입력: nums = [2,3,4], queries = [0,2,2]

출력: [1,2,2]

설명:

gcdPairs = [gcd(nums[0], nums[1]), gcd(nums[0], nums[2]), gcd(nums[1], nums[2])] = [1, 2, 1]입니다.

이를 오름차순으로 정렬하면 gcdPairs = [1, 1, 2]가 됩니다.

따라서 정답은 다음과 같습니다.

[gcdPairs[queries[0]], gcdPairs[queries[1]], gcdPairs[queries[2]]] = [1, 2, 2]

---

제한

• $2 <= n == nums.length <= 10^5$
• $1 <= nums[i] <= 5 * 10^4$
• $1 <= queries.length <= 10^5$
• $0 <= queries[i] < n * (n - 1) / 2$

---

풀이

적당한 전처리를 하면 쿼리를 이분탐색으로 해결할수 있다.

1. 먼저 주어진 nums 배열을 카운팅한다.
2. d 배열을 하나 만든다.

d 배열의 내용은 다음과 같이 한다.

• d[1] : nums에서 1의 배수의 갯수
• d[n] : nums에서 n의 배수의 갯수

어라 그런데 이러면 시간복잡도 초과 아닌가?
아니다! 왜냐?

d[1]의 경우는 어느정도 맞다, nums의 최댓값이 M이라고 했을때 M번 연산하기 때문
하지만 d[2]만 되어도 M/2 번의 연산을 할것이고
d[n]의 경우 M/n의 연산을 하기때문에

M + M/2 + M/3 + ... 이 되어 MlogM에 유사한 시간복잡도로 구할수 있다.

그 다음에 각 d의 값으로 만들수 있는 쌍의 갯수로 변경한다.

즉 d[n]을 n의 배수로 만들수 있는 쌍의 갯수로 변환한다.

$d[n] = (d[n] * (d[n] + 1)) / 2$

그런데 이러면 2의 배수로 만들수 있는 쌍에는 4의 배수로 만들수 있는 쌍이 포함되는 등의 문제가 생길것이다.

이를 해결하기 위해 d[n] 으로부터 d[n*2] ... d[M에 가까운것] 을 전부 빼준다.

다만 d[2]같이 작은값으로부터 d[4], d[8] 등을 빼면 [4, 8]과 같은 경우 중복된 쌍을 제거할수도 있기 때문에 큰값부터 제거해주면 된다.

그러면 우리가 얻는것은 꽤나 인상적인것이 된다.
d[n]은 최대 n의 배수로만 표현 가능한 숫자 쌍들 만 남게 된다!
즉 d[n]은 n을 최대공약수로 가지는 숫자의 갯수가 되는것이다!

이렇게 구한 d의 prefix sum을 만들면 해당 숫자에 대해 몇개나 값들이 쌓였는지를 확인할수 있는 정렬된 배열이 만들어지고

이를 이용해 쿼리의 q로 이진탐색, 해당 index의 값을 바로 구할수 있다!

class Solution:
    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:
        cntr = Counter(nums)
        M = max(nums)
        d = [0] * (M + 1)

        for i in range(1, M + 1):
            for j in range(i, M + 1, i):
                d[i] += cntr[j]

        for i in range(M + 1):
            d[i] = (d[i] * (d[i] - 1)) // 2

        for i in range(M, 0, -1):
            for j in range(i * 2, M + 1, i):
                d[i] -= d[j]

        prefix = [0] * (M + 1)

        for i in range(1, M + 1):
            prefix[i] = prefix[i - 1] + d[i]

        ans = []

        for q in queries:
            ans.append(bisect_left(prefix, q + 1))

        return ans