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

참고 내역

최대공약수(GCD), 최소공배수(LCM) 구하기 유클리드 호제법 알고리즘 :: 코드자몽

 

정리

일단, A, B 의 최소공배수는

"A * B / 최대공약수" 로 구할 수 있습니다.

최대 공약수는 자연수 1 ~ N 까지 두수에 나눠서 모두 나눠 떨어진다면 구할 수 있습니다.

하지만 시간 복잡도가 O(N) 으로 효율적이지 못하죠.

여기서 유클리드 호제법을 이용하면 O(logN) 으로 단축시킬 수 있습니다.

알고리듬을 나열하면 아래와 같습니다.

 

1. 큰 수에서 작은 수를 나눠 나머지를 구함

2. 만약 나머지가 0이 아니면, 큰 수를 나머지 값으로 대체하고

   0 이면, 이전에 나눈 수가 최대 공약수  ===================> 반복 탈출

3. 큰 수를 나머지 값으로 대체하고 다시 나눠 반복

 

나머지를 재사용해서 시간을 단축시킵니다.

코드

#include<iostream>
using namespace std;

int main() {

	int A, B;
	
	cin >> A >> B;

	if (A < B) {
		A ^= B;
		B ^= A;
		A ^= B;
	}

	int remainder;
	int tmpA = A;
	int tmpB = B;
	while (true) {

		remainder = tmpA % tmpB;

		if (remainder != 0) {
			tmpA = tmpB;
			tmpB = remainder;
		}
		else {
			break;
		}
	}
	
	cout << tmpB << endl;
	cout << A * B / tmpB;

	return 0;
}