유클리드 알고리즘 [알고리즘 공부][정수론]

유클리드 알고리즘이란 정수 a와 b의 최대공약수 gcd(a,b)를 효율적으로 계산하는 방법이다.

다음과 같은 공식을 기반으로 한다.

def gcd(a,b):
    if(b==0): return a #만약 b가 0이라면 a=최대공약수
    return gcd(b,a%b) #b와 a를 b로 나눈 나머지의 최대공약수

이 알고리즘이 올바르게 작동하는 이유는 최대공약수 x는 a와 b 모두의 약수이기 때문에 a mod b의 약수이기도 하기 때문이다.

이 알고리즘을 이용하여 시간복잡도를 O(log n)까지 줄일 수 있다.

 

이를 이용한 연습문제를 하나 풀어보고 마치겠다.

 

2981 - 검문(골드 4)

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

n개의 수가 주어졌을때 이 수들을 나누었을때 나머지가 모두 같은 모든 m을 찾아내야 한다.

모든 m을 찾으라는 의미는 가장 큰 m의 약수를 찾으라는 의미와 같다.

즉 우리는 가장 큰 m, 즉 최대공약수만 찾아주면 된다.

이때 n개의 수가 전부 나머지가 같다고 하였으므로

n1 = a1*m+b, n2 = a2*m+b ... 이므로 

서로 빼준 값들을 구해주면 전부 m의 배수들이 나오게 된다!

이를 이용하여 빠르게 최대공약수를 구해주면 된다.

n=int(input())
l=[]
for i in range(n):l.append(int(input()))
l.sort()

t=[]
for i in range(n-1):t.append(l[i+1]-l[i])#서로 빼줌으로써 나머지 제거
t.sort()

def gcd(a,b):#유클리드 알고리즘
    if(b==0): return a
    return gcd(b,a%b)
for i in range(n-2):
    g=gcd(t[0],t[1])#최대공약수
    t=[g]+t[2:]#다음 값과 최대공약수 비교
for i in range(2,t[0]+1):#약수 출력(1 제외)
    if(t[0]%i==0):print(i,end=' ')