[C++][백준 5347] LCM

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

풀이

최소공배수(LCM)와 최대공약수(GCD)를 유클리드 호제법을 이용해 푸는 문제다

 

두 수의 최소 공배수는 두 수의 곱을 최대 공약수로 나누면 구할 수 있다

 

a와 b의(단, a > b)최대 공약수는 a % b(mod), 즉 나머지가 0이 될 때까지 아래와 같이 반복하여 구할 수 있다

1. a % b = r, 나머지의 값을 구한다

2. b를 나머지(r)로 나눈 값의 나머지(r')를 구한다

3. r을 r'로 나눈 값의 나머지(r'')를 구한다

...

 

 

제출 코드

#include <iostream>
using namespace std;

long long gcd(long long a, long long b)
{
    if (a % b == 0)
        return b;
    return gcd(b, a % b);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    long long n, a, b;
    cin >> n;
    while(n--)
    {
        cin >> a >> b;
        cout << (a * b) / (a > b ? gcd(a, b) : gcd(b, a)) << '\n';
    }
}