[C++] 백준 13241번 - 최소공배수

 

문제 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;
}