[유클리드 호제법 / python] 백준 2981. 검문

https://www.acmicpc.net/problem/2981

2981번: 검문

 

algorithm_type	math(정수론, 유클리드 호제법)
is_clear	False

 

 

문제 풀이

이 문제는 정말 "수학적인 사고"를 요하는 문제였다. 주어지는 숫자들은 모두 같은 숫자로 나눠서 같은 나머지를 가져야 하므로, 각 숫자들은 동일한 나머지 값을 뺀 상태에서 공약수가 존재한다는 의미이다.

따라서, 우리는 저 m이 어떤 수인지 알아내면 된다. 그러면 우리가 고등학교 때 x를 구했던 것 처럼, m을 구하기 위해 식을 정리해보자.

위 식에서 볼 수 있듯이, B-A 와 C-B 또한 m을 공약수로 갖는 수라는 것을 알 수 있다. 따라서 우리는 m을 모두 알아내면 되고, 이는 m이 최대공약수가 되는 값을 구한 뒤 그 최대공약수 m의 약수를 구하면 우리가 원하는 정답을 얻을 수 있다. 이때, 최대공약수를 구하는 방법으로 유클리드 호제법을 사용한다. 유클리드 호제법은 두 개의 큰 수의 최대공약수를 작은 수의 최대공약수를 구하는 문제로 만드는 알고리즘이다.

 

https://www.youtube.com/watch?v=K-DwxHl1eJY 

유클리드 호제법의 증명

유클리드 호제법을 코드로 옮기면 다음과 같다.

def GCD(a,b):
    # a > b라고 가정
    while 1:
        res = a % b
        if res == 0: break
        a = b
        b = res
    return b

 

준비는 끝났다. 이를 이용하여 백준 문제를 풀어보자.

def GCD(a,b):
    # a > b라고 가정
    while 1:
        res = a % b
        if res == 0: break
        a = b
        b = res
    return b

t = int(input())
li = sorted([int(input()) for i in range(t)])

_li = list()

for i in range(len(li)-1):
    _li.append(li[i+1]-li[i]) # B-A, ... 저장
_li.sort()

m = _li[0]
for i in range(1, len(_li)):
    m = GCD(_li[i], m)
ans = set()
for i in range(2, int(m**0.5)+1):
    if m % i == 0:
        ans.add(i)
        ans.add(m//i)
ans.add(m)
print(*sorted(ans))