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

유클리드 호제법에 대해서 기억해두자!
A = qB + r 이라고 할 때
GCD(A, B) = GCD(B, r) 이라는 점을 이용하여 계속 축소해서 답을 구하는 방식이다.
나눈 몫이 0이 될때까지 계속해서 작업한다.

이 논리는 두 수 A, B (A < B, A != B) 를 최소공배수 g를 사용하여
A = ga, B = gb 라고 표현했을 때 (a, b는 서로소여야 g가 최소공배수)

A = qB + r
-> ga = qgb + r
-> r = ga - qgb = g(a - qb) = gr'
이렇게 표현할 수 있으므로 r 역시 g의 배수이다.

그렇다면 GCD(A, B) = GCD(B, r) 을 증명하려면
B = gb, r = gr' 이므로 GCD(b, r') = 1 이라면 (서로소라면)
B와 r의 역시 최소 공배수로 g를 갖는 것이다.

GCD(b, r') != z (z != 1) 이라고 가정해보면
A = qB + r / A = ga, B = gb, r = gr' / b = zb', r' = zr''
-> ga = qgb + r
-> ga = qgb + gr'
A = ga = qgzb' + gzr'' = gz(qb' + r'') 이 되어 g가 최소공배수가 될 수 없는 상황이 발생하므로
z 는 1이어야만 한다.

증명과정보다는 구하는 것이 더 많이 나올 것 같으므로
외우도록 해보자

#include <iostream>
using namespace std;

int GCD(int a, int b)
{
	if (b == 0)
	{
		return a;
	}

	return GCD(b, a % b);
}

int LCM(int a, int b)
{
	return (a*b)/ GCD(a, b);
}

int main()
{
	int N, M;
	cin >> N >> M;

	if (N >= M)
	{
		cout << GCD(N, M) << "\n";
		cout << LCM(N, M) << "\n";
	}
	else
	{
		cout << GCD(M, N) << "\n";
		cout << LCM(M, N) << "\n";
	}

	return 0;
}