프로그래밍 공부/백준 (C++)
[C++/ 백준 13241번] 최소공배수
Rocketbabydolls
2023. 8. 17. 20:16
https://www.acmicpc.net/problem/13241
13241번: 최소공배수
정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다
www.acmicpc.net
해결방법
유클리드 호제법으로 해결했다.
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
long long int euclid(long long int a, long long int b)
{
if (a % b != 0)
{
return euclid(b, a % b);
}
else
{
return b;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
long long int A, B;
cin >> A >> B;
long long int num;
long long int cnt = 0;
for (int j = 1; j <= (A > B ? A : B) ; j++)
{
if ((A % j == 0) && (B % j == 0))
{
cnt++;
}
}
long long int max_div = euclid((A < B ? A : B), (A > B ? A : B));
if (cnt == 1)
{
num = A * B;
}
else
{
num = (A * B / max_div);
}
cout << num << '\n';
return 0;
}