BOJ 2981 검문

문제 구조화

주어진 숫자들을 정렬한 결과가 $a_1, a_2,...,a_n$ 이라 하자. 그럼 문제의 조건을 만족하는 $M$은 다음과 같이 나타내어질 수 있다.

이때 나머지 $r$을 없애주기 위해 인접하는 원소의 차이를 구하는 것이 이 문제의 핵심이다.

$a_i$는 전부 unique하므로 $(a_i-a_j)$는 전부 자연수이다. 따라서 위 수식을 만족하는 $M$은 $(a_i-a_j)$의 공약수들이므로, 최대공약수를 구한 후 약수를 구하면 된다.

셋 이상의 수의 최대공약수

숫자가 둘일 경우 유클리디언 호제법을 이용해서 최대공약수를 쉽게 구할 수 있다.

def gcd(a: int, b: int):
    if b == 0:
        return a
    return gcd(b, a % b)

숫자의 수가 3 이상일 경우 반복적으로 위 알고리즘을 적용하면 된다. 즉 두 숫자의 최대공약수를 구한 후 그 최대공약수와 다음 숫자의 최대공약수를 구한다.

while len(arr) > 1:
    a = arr.pop()
    b = arr.pop()
    arr.append(gcd(a, b))

약수 구하기

$n$의 약수는 2부터 $\sqrt{n}$까지 반복해 $n$을 그 수로 나눈 나머지가 0이면 배열에 저장한다. 이때 {i, n // i} 를 모두 저장해야 한다.

answers = []
for i in range(2, int(n ** (1 / 2)) + 1):
    if n % i == 0:
        if (i ** 2) == n:
            answers.append(i)
        else:
            answers.extend([i, n // i])

완성 코드

import sys

input = sys.stdin.readline

N = int(input())
arr = [int(input()) for _ in range(N)]
arr.sort()
new_arr = []
for i in range(1, len(arr)):
    new_arr.append(arr[i] - arr[i - 1])

new_arr = list(set(new_arr))


def gcd(a: int, b: int):
    if b == 0:
        return a
    return gcd(b, a % b)


while len(new_arr) > 1:
    a = new_arr.pop()
    b = new_arr.pop()
    new_arr.append(gcd(a, b))

n = new_arr[0]
answers = []
for i in range(2, int(n ** (1 / 2)) + 1):
    if n % i == 0:
        if (i ** 2) == n:
            answers.append(i)
        else:
            answers.extend([i, n // i])
answers.append(n)
answers.sort()
print(*answers)