[백준/C++] 5347번 LCM

문제링크

5347번 LCM

 

유클리드 호제법을 통해 최대공약수를 구현하고 최소공배수를 구하는 문제

최소 공배수는 두 수의 곱을 최대공약수로 나눈 값으로 구할 수 있다.

 

제출코드

#include <iostream>

using namespace std;

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

long long gcd(long long a, long long b);
long long lcm(long long a, long long b);

int main() {
    long long a, b;
    long long n;
    cin >> n;
    while (n--)
    {
        cin >> a >> b;
        cout << lcm(a, b) << '\n';
    }
    return 0;
}

long long gcd(long long a, long long b)
{
    long long A, B;
    if (a > b)
    {
        A = a;
        B = b;
    }
    else
    {
        A = b;
        B = a;
    }
    if (B == 0)
    {
        return A;
    }
    return gcd(B, A % B);
}

long long lcm(long long a, long long b)
{
    return (a * b) / gcd(a, b);
}