최대공약수와 최소공배수
수학 관련 문제에서 가장 많이 사용하는 것은 이전 글인 소수와 최대공약수인 것 같다.
보통 최대 공약수를 구하는 문제에서는 유클리드 호제법을 이용한 알고리즘을 사용한다.
시간 복잡도는 O(lonN)이고, 이 글에서는 간단하게 증명을 해보려고 한다.
증명
A와 B라는 두 숫자의 최대 공약수 G를 구해보자.
증명할 내용은 a를 b로 나눈 나머지를 r이라고 할 때 A와 B의 최대 공약수는 B와 r의 최대 공약수와 같다는 것이다.
우선 A = a * G, B = b * G로 표현할 수 있다.
A와 B의 최대 공약수가 G라면 a와 b는 서로소여야만 한다.
A를 B로 나누면 A = qB + r이고, aG = q*bG + r이다.
r에 대해 정리하면 r = (a-qb)G이다. B와 r의 최대 공약수가 G려면 b와 (a-qb)가 서로소여야 한다.
귀류법으로 b와 (a-qb)가 n이라는 공약수를 가진다고 가정하면 (a-qb) = xn, b = yn이다.
b = yn이므로 (a-qyn) = xn이고, a에 대해 정리하면 a = (x+qy)n이다.
이러면 a = (x+qy)n이고 b = yn이므로 a와 b는 n이라는 공약수를 가지게 된다.
맨 처음 조건인 a와 b가 서로소라는 조건에 모순되므로 b와 (a-qb)가 공약수를 가진다는 가정은 모순이 생긴다.
그러므로 b와 (a-qb)는 공약수가 없는 서로소 관계이고, B와 r의 최대 공약수는 G이다.
A와 B의 최대 공약수와 B와 A%B=r의 최대 공약수가 같으므로 반복문을 통해 쉽게 구할 수 있다.
a가 b보다 클 때, 밑의 반복문을 반복해보자.
1
2
3
4
5
6
while(b)
{
c = a % b;
a = b;
b = c;
}
b는 계속 감소하므로 언젠가 0이 되고, 임의의 수 n과 0의 최대 공약수는 n이다.
이렇게 A와 B의 최대 공약수는 B와 r의 최대 공약수와 같다는 사실을 이용해 쉽게 최대 공약수를 구할 수 있다.
코드로 보면
1
2
3
4
5
6
7
8
9
10
11
int gcd(int a, int b)
{
int c;
while(b)
{
c = a % b;
a = b;
b = c;
}
return a;
}
이다.
같은 방법으로 정수의 최대 공약수뿐만 아니라 다항식들의 최대 차수 공약 다항식도 구할 수 있다.
최소 공배수
A = a * G, B = b * G에서 A와 B의 최소 공배수는 a * b * G이다.
A * B = a * G * b * G이므로 A와 B를 곱한 후 최대 공약수로 나누면 최소 공배수를 구할 수 있다.