[백준] 5474번 LCM / C++ Java

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

C++

#include<iostream>
using namespace std;

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

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

    long n,a,b,ta,tb; cin >> n;
    long total = 0;

    while(n--) {
        cin >> a >> b;
        ta = (a / check(a,b));
        tb = (b / check(a,b));
        total = check(a,b) * ta * tb;
        cout << total << endl;
    }
    return 0;
}

Java

import java.util.Scanner;

public class Main {
    public static long check(long a, long b) {
        if(a % b == 0) {
            return b;
        }
        return check(b, a % b);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        for(int i = 0; i < n; i++) {
            long a = sc.nextLong();
            long b = sc.nextLong();

            long gcd = check(a,b);
            long ta = (a / gcd);
            long tb = (b / gcd);

            System.out.println(ta * tb * gcd);
        }
        sc.close();
    }
}

문제풀이

• 두 수의 최소공배수를 구해야하기 때문에, 먼저 최대 공약수를 구한다. 최대 공약수를 구한 뒤, 두 수를 최대 공약수로 나눈 값들과 최대 공약수를 곱하면 된다.

Comment

• 유클리드 호제법을 사용해서, 큰 어려움 없이 문제를 풀었다.