1934_최소공배수(C++)

#include <iostream>
using namespace std;

int gcd(int a, int b) {
	while(b!=0){
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}
int lcm(int a, int b) {
	int g = gcd(a, b);
	int l = (a / g) * (b / g) * g;
	return l;
}

int main() {
	int t, a, b;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> a >> b;
		cout << lcm(a, b) << '\n';
	}
}

2609번과 비슷한 풀이이다.
2609번 풀이 참고.
https://velog.io/@kimeunseo58/2609%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98%EC%99%80-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98C
유클리드 호제법을 이용하여 gcd를 구한 후, gcd를 이용하여 lcm을 구해준다.

좋은 웹페이지 즐겨찾기