[백준/BOJ] 13241번 최소공배수 (C/C++)

백준 온라인 저지(BOJ) 13241번 최소공배수

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

13241번: 최소공배수

* 사용언어 : C언어, C++

 

1. 문제

100,000,000 미만의 두 수 A, B의 최소공배수 출력

 

2. 풀이

유클리드 호제법을 활용하여 최대공약수(GCD)를 구한 후

A * B == GCD * LCM 임을 활용하여 답을 출력합니다.

 

long long int가 아닌 int로 처리할 경우,

A * B를 하는 과정에서 Overflow가 발생할 수 있습니다.

문제에서 제시해준 것처럼 long long int로 사용하시면 정답 처리됩니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
13241_최소공배수
1112KB	0ms
*/
#include <cstdio>
using LL = long long;

int gcd(LL a, LL b) {
	LL r;
	while (1) {
		r = a % b;
		if (r == 0) break;
		a = b;
		b = r;
	}
	return b;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	LL a, b;
	scanf("%lld %lld", &a, &b);
	if (a < b) {
		LL t = a;
		a = b;
		b = t;
	}

	printf("%lld\n", a * b / gcd(a, b));
	return 0;
}