BOJ - 1934 최소공배수

 

해결방법

먼저 최대공약수와 최소공배수에 대해 정의를 알아보자.

어떤 두 수가 공통으로 나눌 수 있는 가장 큰 정수를 최대공약수라고 하고,

어떤 두 수의 배수 중에서 가장 작은 공통 배수를 최소공배수라고 한다.

 

예를 들어 12와 18의 최대공약수를 구한다면

1, 2, 3, 4, 6, 12가 12의 약수,

1, 2, 3, 6, 9, 18이 18의 약수이므로,

공통약수 1, 2, 3, 6중 6이 최대공약수가 된다.

여기서 유클리드 알고리즘을 적용하여 최대공약수를 쉽게 구할 수 있는데, 다음과 같다.

 

두 수 A와 B에서, A > B일 때, A와 B의 최대공약수는 A % B와 B의 최대공약수와 동일하다.

이 과정을 나머지가 0이 될 때까지 반복하면, 그때의 B 값이 최대공약수가 되는데, 

예를 들어 방금전의 12와 18을 예시로 들면 18%12는 1...6이 되고, 12%6은 2...0이 되므로 최대공약수는 6이 된다.

 

최소공배수의 경우 다음과 같은 공식을 이용하여 구한다.

최소공배수 = (A × B) / 최대공약수

 

 

정답 코드

#include <iostream>

using namespace std;

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

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

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

    for (int i = 0; i < T; i++)
    {
        int A, B;
        cin >> A >> B;

        cout << lcm(A, B) << endl;
    }

    return 0;
}