1. 문제

---

출처: 백준 2981번 검문

2. 풀이

---

숫자들이 너무 크기 때문에, 그대로 일일이 계산한다면 시간 초과가 발생할 수밖에 없다.

따라서, 유클리드 호제법을 적극 활용해야 한다.

유클리드 호제법

두 양의 정수 $a,b$ $(a > b)$에 대하여 $a=bq+r$ $(0\leq r<b)$이라 하면, $a,b$의 최대공약수는 $b,r$의 최대공약수와 같다. 즉,

$gcd(a,b) = gcd(b,r)$

$r=0$이라면 $a,b$의 최대공약수는 $b$가 된다.

그리고, 같은 나머지를 가지는 숫자를 구하는 것이므로, 주어진 숫자들의 차이로 리스트를 만들고 이들의 공약수를 구해도 된다.

$A=GQ_1+r$이고 $B=GQ_2+r$일 때, $A-B = G(Q_1-Q_2)$ 이다.

모든 차이들에 대해서 최대공약수를 구하고 최대공약수의 약수들을 구해서 출력해 주면, 문제에서 요구하는 나머지가 모두 같게 되는 $M$들을 구할 수 있다.

약수를 구하는 과정에서 시간 초과가 뜨지 않도록, 유의해 준다.

3. 소스코드

---

case = int(input())
number = []
for _ in range(case):
    number.append(int(input()))

#유클리드 호제법
def gcd(a,b):
    A = max([a,b])
    B = min([a,b])
    if A%B == 0:
        return B
    else:
        return gcd(B,A%B)

#숫자 차이들의 최대공약수를 구하자 
test = []
for l in range(len(number)-1):
    test.append(abs(number[l]-number[l+1]))
number = test

#단 하나의 최대공약수가 남을 때까지 반복
while len(number)!=1:
    number_edit = set()
    for i in range(len(number)-1):
        number_edit.add(gcd(number[i],number[i+1]))
    number = list(number_edit)

M = {number[0]}
for k in range(2,number[0]):
    if k > number[0]//k:
        break
    if number[0] % k ==0:
        M.add(k)
        M.add(number[0]//k)
M=list(M)
M.sort()
print(*M, sep=" ")

4. 그 외

---

오래간만에 정수론 문제를 푸니, 중학교 때 기억이 새록새록 났다.
숫자들이 커서 시간 초과가 나는 경우가 많아서, 다른 분들의 풀이를 참고해서 숫자를 줄여나가는 과정을 배울 수 있었다.