[C++] 2609번 최대공약수와 최소공배수

2609번: 최대공약수와 최소공배수 (acmicpc.net)

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

---

난이도 : 실버 5

 

풀기 전 알아야 할 개념 :

최대공약수와 최소공배수의 개념을 알고 그냥 풀 수도 있기는 한데요,

최대공약수는 두 수를 1부터 N까지 계속 나누면서 공통적으로 나머지가 0이 나오는 값중에 가장 큰 값이고,

최소공배수는 두 수를 최대 공약수로 나눠서 둘이 곱해준 값입니다.(왜냐면 두 수의 최대공약수로 나누면 그 수가 서로소가 가 되기 때문에, 서로소를 곱한 값이 최소 공배수가 되기 때문)

 

근데 이렇게 하면 시간복잡도가 유클리드호제법을 이용한 것보다 크다고 합니다.

그래서 유클리드 호제법을 이용하여 푸는 것이 더 효율적입니다.

 

유클리드 호제법 <-[Algorithm] 유클리드 호제법 - 최대공약수(GCD) 구하기 (tistory.com)

[Algorithm] 유클리드 호제법 - 최대공약수(GCD) 구하기

이 글 참고하시면 잘 이해되실 거같네요 저도 이거보고 이해했습니다!!

 

답 :

#include <iostream>
int gcd(int a, int b) {
	while (b != 0) {
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int main() {
	int a, b;
	scanf("%d %d", &a, &b);
	printf("%d\n", gcd(a, b));
	printf("%d", a * b / gcd(a, b));
}