백준 2609번 최대공약수와 최소공배수

< 백준 2609번 최대공약수와 최소공배수 - 마포 코딩박 >

사용한 알고리즘: 수학


 두 수 a, b 사이의 gcd 를 구하는 법을 묻는 문제였습니다.

a, b 사이의 gcd를 구하는 법은 다음과 같습니다.
b = a*D + R , D: 몫, R: 나머지 라고 한다면 a 와 a*D 의 gcd 는 a 이므로,
gcd(b,a) = gcd(a,R) 입니다.

따라서 gcd(b,a) = gcd(a, b%a) = .... 로 재귀적인 방법을 이용하여 gcd를 구해주면 됩니다.
한쪽이 0 이 나올때 까지 재귀를 계속 돌리면 됩니다.

a,b의 gcd = g 라 하면, a = g*A, b = g*B , ( A,B는 g 로 나누어지지 않는다 ) 이므로
a,b의 최소공배수는 A*B*g = (g*A*g*B)/g = a*b/g 입니다.

	#include <bits/stdc++.h>
	using namespace std;
	int GCD(int x, int y){
	if(y==0) return x;
	else return GCD(y, x%y);
	return 0;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	int a, b;
	cin >> a >> b;
	int G = GCD(a,b);
	cout << G << '\n' << a*b/G << '\n';
	return 0;
	}

view raw BOJ 2609.cpp hosted with ❤ by GitHub