[백준 5347번] LCM (C++)

문제링크 : https://www.acmicpc.net/problem/5347

5347번: LCM

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

ll N, a, b;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    while(N--)
    {
        cin >> a >> b;
        ll tmp = gcd(a, b); //최대공약수 구하기
        cout << tmp * a/tmp * b/tmp << "\n";
    }


}

 

최소공배수를 구하는 방법은 최대 공약수에 a와 b에 대한 각 서로소의 값을 곱해주는 것이다.

우선 최대공약수의 경우 gcd 함수로 쉽게 구할 수 있다.

a, b에 대해 미리 구했던 최대공약수로 나눠주면 a, b에 대한 각 서로소를 구할 수 있다.

따라서 이 값들을 차례로 곱해주면 된다. (최대공약수 * a/최대공약수 * b/최대공약수)

 

각 a, b는 100만까지 범위를 가지므로 최소공배수의 값이 int 범위를 초과하는 경우가 생긴다.

따라서 관련된 값들을 long long으로 선언해주어야 한다.