[BOJ] 13241번: 최소공배수

13241번: 최소공배수

풀이

gcd와 lcm을 알고 있으면 되는 문제다. 

최소공배수는 주어진 정수 a, b에서 lcm(a, b) = a * b / gcd(a, b)이다.

최대공약수는 유클리드 호제법을 사용하면 된다.

정수 m, n(m > n)이 주어질 때 gcd(m, n)은

long long int gcd(long long int a, long long int b)
{
    return b ? gcd(b, a % b) : a;
}

다음과 같이 구현할 수 있다. 자세한 내용과 증명 과정은 링크를 참고하면 된다.

코드

#include <cstdio>
 
long long int gcd(long long int a, long long int b)
{
    return b ? gcd(b, a % b) : a;
}
 
long long int lcm(long long int a, long long int b)
{
    return (a * b) / gcd(a, b);
}
 
int main()
{
    long long int a, b;
    scanf("%lld %lld", &a, &b);
 
    long long ans = lcm(a, b);
    printf("%lld", ans);
    return 0;
}