[BOJ] 백준 1934 최소공배수

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

Approach

두 수가 주어지면 최소공배수(Least Common Multiple, LCM)를 구하는 문제이다.

문제에서 설명한대로 최소 공백수의 정의를 이용해서

반복문으로 단순하게 구현할 수도 있지만

 

최대 공약수(Greatest Common Divisor, GCD)는

유클리드 호제법(Euclidean Algorithm)을 이용하여 구할 수 있다.

또한 최대 공약수를 통해서 최소공백수(LCM)를 쉽게 구할 수 있다.

→ LCM = A * B / GCD(A, B)

 

ex) 10과 50의 최소공배수 = 50 일 때,

      10과 50의 최대공약수 = 10

       → 최소공배수 (LCM) = 50 = 10 * 50 / 10

 

정답 출력시에는 별도 배열에 저장하지 않고 바로 출력해도 관계없다.

백준 문제 사이트에서 입력과 출력은 별개로 처리하기 때문이다.

 

---

#include <iostream>

using namespace std;

int GCD(int a, int b) 
{
	return b == 0 ? a : GCD(b, a % b);
}

int main(void) 
{
	// freopen("input.txt", "r", stdin);
	int T, A, B;
	
	cin >> T;
	while (T--) 
	{
		cin >> A >> B;
		cout << A * B / GCD(A, B) << endl;
	}
}