백준 5347번 LCM C++

리뷰

변수 형식 지키기가 너무나 어렵다... 휴

 

문제 풀이

1. 테스트 케이스의 개수 n과 정수 a, b에 값을 받아주고 lcm 함수에 a, b를 인자로 넣어준다.
2. a, b중 작은 값을 gcd로 초기화 하고, a를 gcd로 나눈 값과 b를 gcd로 나눈 값이 모두 0이 될때까지 gcd를 빼준다.
3. while루프를 벗어났을때 a, b중 큰 값과 a와 b를 변경된 gcd로 나눈 값 중 작은 값을 곱해준 뒤 리턴해 준다.
4. lcm 함수로부터 리턴받은 값을 출력해 준다.

 

참고 사항

두 수의 범위가 1,000,000 미만이므로 int 형식으로는 오버플로우가 난다, 리턴 시 long long 형식으로 바꿔준다.

 

 

정답 코드

#include <iostream>

using namespace std;

long long lcm(int a, int b) {
	int gcd = min(a, b);
	while (a % gcd || b % gcd) {
		gcd--;
	}
	return (long long)max(a, b) * min(a / gcd, b / gcd);
}


int main() {
	int n;
	cin >> n;
	while (n--) {
		int a, b;
		cin >> a >> b;
		long long ans = lcm(a, b);
		cout << ans << "\n";
	}
}