1934번: 최소공배수 [C++]

문제

 

 

풀이

유클리드 호제법을 이용해 a와 b의 최대공약수를 구한 뒤 a와 b의 곱에 최대공약수를 나눈 몫이 최소공배수가 된다.

#include <iostream>

using namespace std;

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

int main() {
	int n;

	cin >> n;

	for (int i = 0; i < n; i++) {
		int a, b;

		cin >> a >> b;

		cout << a * b / gcd(a, b) << "\n";
	}

	return 0;
}