[C/C++] 백준 2609번 - 최대공약수와 최소공배수 (유클리드 호제법과 증명)

<코드>

#include<iostream>
#include<algorithm>
using namespace std;

int a,b,tmp;

int GCD(int x, int y) // 최대공약수
{
	if (y == 0) {
		return x;
	}
	else {
		return GCD(y, x % y);
	}
}

int LCM(int x, int y) // 최소공배수
{
	return x * y / GCD(x, y);
}


int main()
{
	cin >> a >> b;
	tmp = GCD(a, b);
	cout << GCD(a, b) << endl << LCM(a, b);
}

유클리드 호제법을 사용하면 시간 초과 없이 빠르게 처리가 가능하다.

 

 

유클리드 호제법

유클리드 호제법을 이용하면 최대공약수를 빠르게 구할 수 있습니다. 자세한 설명은 링크를 참고해주시면 되겠습니다.

유클리드 호제법을 요약하자면 GCD(x, y)에서 x mod y 가 0이라면 GCD(x, y) = y이게 됩니다. 만약에 x mod y 가 0이 아닐 경우에는 GCD(x, y) = GCD(y, x mod y)가 성립하게 된다.

증명

x mod y = r이라 한다면

x = qy + r로 표현할 수 있고 

GCD(x, y) = GCD(y, r) 인지 확인하기 위해 

x = Gx', y = Gy' (x', y'는 서로소)

Gx' = qGy' + r

즉, r = G(x' - qy')이고  y = Gy'이다.

여기서 r과 y가 G라는 공약수를 갖는데 이 공약수가 최대공약수임을 증명하면 되니까

x' - qy'와 y'가 서로소임을 증명해야 한다.

만약 서로소가 아니라면 p라는 공약수를 갖고 아래와 같이 표현되는데,

x' - qy' = np 그리고 y' = mp이고 다시 식을 쓰면

x' - qmp = np

x' = p(n + qm)으로 정리될 수 있다. 그러나 y' = mp이며 x'와 y'는 서로소인데 p라는 공통 약수를 가지므로

서로소가 아니라는 가정에 위배된다. 따라서 x' - qy'와 y'가 서로소이며 y와 r의 최대공약수는 G이다.

따라서, GCD(x, y) = GCD(y, r) = GCD(y, x mod y)가 성립하게 된다.

 

 

 

www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수