[백준/2609] 최대공약수와 최소공배수| 유클리드 호제법 | 확장 유클리드 알고리즘

유클리드호제법(최대공약수와 최소공배수)

두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법이다. 호제법이라는 말은 '서로 나눈다'라는 뜻. 일반적으로 우리는 최대공약수를 구할 때 소인수분해를 하고 두 수의 공통인 소인수를 곱한다. 이 방법은 수가 커질수록 소인수분해하기 어려워진다는 단점이 있다. 이를 극복하기 위한 방법이 유클리드 호제법이다.

 

그렇다면, 유클리드 알고리즘을 어떻게 구현할 수 있을까?

바로 mod 연산(나머지 구하기 : %)을 반복하는 방법이다.

 

why mod p?

• 답이 큰 정수인 경우, Overflow 에러를 막기 위해서 문제에서 큰 소수(보통 1,000,000,007)로 나눈 나머지를 요구

자연수 a, b에 대해 a를 b로 나눈 나머지는 r이다. (단 a>b)

r에 대해, b를 r로 나눈 나머지 r'를 구한다. 나머지가 0이 될 때 까지 이 과정을 반복하고,

나머지가 0이 될 때 나누는 수 r^n이 a와 b의최대공약수이다.

즉,  a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 

쉬운 예를 들어보았다

즉 gcd(40, 35) = gcd(35, 5) = gcd (5,0)이다. b가 0이 되는 순간의 a(5)가 40과 35의 최대공약수이다.

💡 gcd(a,b) = gcd(b,r) = ... = gcd(b,0)일 때 최대공약수는 b.

 

 

---

확장 유클리드 알고리즘

소수 p와, p의 배수가 아닌 자연수 a가 주어졌을 때, ab = 1(mod p)가 되는 b를 구해보자.

ax + by = GCD(a, b)가 되는 경우가 있다.

---

소인수분해와 시간 비교

O(log max(a,b)) 시간

둘 중 큰 값에 log를 취한 값만큼ㅁ만 시간 걸림

항상 큰 쪽에서 작은 쪽에서 뺀 차를 이용하기 때문.

어떤때는 ? 뺀 차가 작은 값보다 더 큰 경우가 있다.

차가 작은 수보다 작아질 때까지 빼야한다.

피보나치수 ,. 뺄 때마다 대소 관계가 바뀐다.

---

최소공배수

결론만 바로 언급하자면 a와 b의 곱을 a와 b의 최대공약수로 나눈 값이다.

최대공약수는 두 수의 공통인 소인수 전체의 곱, 최소공배수는 두 수의 소인수 곱이다.

최대공약수는 a로 나누어도, b로 나누어도 떨어지는 가장 작은 수이기 때문이다.

 

 

---

최대공약수와 최소공배수 유클리드 호제법 파이썬 구현

import sys
a,b= map(int, sys.stdin.readline().split())
x = a*b # 최소공배수 구하기 위한 a와 b의 곱

while b!=0:
    a = a%b # 나머지가 된 a
    a, b = b, a 

print(a) # GCD
print(x//a) #LCM