[백준/C++] 5347 - LCM

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

<numeric> 헤더파일을 include 해주면 gcd, lcm 함수를 사용할 수 있다. 그러나 이는 C++17 이상에서만 지원되기 때문에 직접 구현하는 방법도 알아놔야 되겠다고 생각해서 아래처럼 구현해 보았다.

최소공배수를 직접 구하는것보다 최대공약수를 이용해 최소공배수를 구하는 것이 훨씬 효율적이다. 두 a, b의 최소공배수는 (두 수의 곱 / 두 수의 최대공약수) 라는 공식을 이용해 구할 수 있다.

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int n;
    cin >> n;

    while (n--) {
        long long a, b;
        cin >> a >> b;

        long long g = gcd(a, b);
        long long lcm = a / g * b;

        cout << lcm << "\n";
    }
    return 0;
}