728x90
문제 13241번
https://www.acmicpc.net/problem/13241
A와 B를 곱한 값에 최대공약수를 나눠주면 최소공배수를 구할 수 있다. 이를 위해 유클리드 알고리즘을 이용하여 주어진 두 수 사이에 존재하는 최대공약수(gcd)를 구한다.
a,b가 주어졌을 때(a가 더 큼) 뒷부분이 0일 때 앞 부분이 최대공약수가 된다. 만약 0이 아니라면 a에 b값을 넣고 b에 a%b값을 넣은 후 다시 반복해준다.
#include <iostream>
using namespace std;
long long gcd(long long a, long long b) {
if (b == 0){
return a;
} else{
return gcd(b, a % b);
}
}
int main() {
long long A, B;
cin >> A >> B;
cout << A * B / gcd(A,B);
return 0;
}
728x90
'백준 > C++' 카테고리의 다른 글
[C++] 백준 1292번 - 쉽게 푸는 문제 (0) | 2024.05.24 |
---|---|
[C++] 백준 2805번 - 나무 자르기 (0) | 2024.05.22 |
[C++ 실패하고... 파이썬] 백준 13706번 - 제곱근 (1) | 2024.05.20 |
[C++] 백준 2417번 - 정수 제곱근 (0) | 2024.05.19 |
[C++] 백준 4101번 - 크냐? (0) | 2024.05.18 |