백준 1934 최소공배수

https://www.acmicpc.net/problem/1934

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 두수의 최소공배수를 구하여 출력하는 문제입니다.

 

10과 50의 최소공배수는 50입니다. 이때 이것을 구하는 방법은 10과 50의 최대공약수인 10을 각숫자에 나눈몫들과 곱하면 됩니다.

 

즉 10(gcd) * (10/10) * (50/10) 을 해주면 최소공배수를 구할 수 있습니다.

 

따라서 유클리드 호제법을 이용하여 gcd를 구하고 그것을 이용하여 최소공배수를 구하면 됩니다.

 

 

#include <iostream>

using namespace std;

//최대공약수를 구해서 최대공약수를 이용해 최소공배수를 구함 

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

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int T; cin >> T; 
	int n1,n2;
	
	while(T--) {
		cin >> n1 >> n2;
		int gc = gcd(n1, n2);
		int ans = gc * (n1/gc) *(n2/gc);
		cout<<ans<<'\n';
	}
	return 0;
}