문제 링크

1 초
128 MB

1 ≤ T ≤ 1,000
1 ≤ A, B ≤ 45,000

try1

단순한 반복문을 통한 풀이

#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T, n1, n2, lcm;

    cin >> T;

    while (T--)
    {
        cin >> n1 >> n2;
        lcm = max(n1, n2);

        for (int i = max(n1, n2);; i++)
        {
            if (i % n1 == 0 && i % n2 == 0)
            {
                lcm = i;
                break;
            }
        }

        cout << lcm << '\n';
    }
}

-> 시간초과.

시간복잡도 : O(N)

try2

유클리드 호제법을 통해 최대공약수를 구하고, 두 수를 곱한 값을 구한 최대공약수로 나누어 최소공배수를 구한다.

유클리드 호제법

두 수의 최대공약수를 구하는 알고리즘

호제법

두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘

#include <iostream>

using namespace std;

int gcd(int n1, int n2)
{
    if (n2 == 0)
        return n1;
    else
        return gcd(n2, n1 % n2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T, n1, n2;

    cin >> T;

    while (T--)
    {
        cin >> n1 >> n2;

        cout << n1 * n2 / gcd(n1, n2) << '\n';
    }
}

-> 정답.

시간복잡도 : O(logN)