[BOJ_5347] LCM

설명

---

유클리드 호제법을 이용한다. 최대 공약수를 구하는 식을 이용해서 최대 공약수를 구하고 최소 공배수를 구하기 위해서 각각의 숫자를 곱하고 이를 최대 공약수로 나눈다. 애초에 최대로 공통된 약수를 각각의 숫자로 나누면 공통된 약수중 가장 큰 수로 나누었으니 최소의 공통된 약수를 볼 수 있는 것이므로 이를 이용한다.

 

그리고, 이 사용한 유클리드 호제법은 GCD(a,b)  == GCD(b,r) 을 이용한 것인데, a > b 일때, a/b의 나머지와 더 작은 b의 값이 a,b의 최대 공약수와 동일하다는 것을 이용해서 만든 것이라고 한다. 

 

그리고, 최소 공약수를 구하기 위해서는 이 최대 공약수를 서로 곱한 값의 나눗셈을 위한 값을 사용하면 된다.

 

코드

---

 

package Math;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_5347 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        int T = Integer.parseInt(tk.nextToken());
        while(T-- > 0) {
            tk = new StringTokenizer(in.readLine(), " ");

            long a = Long.parseLong(tk.nextToken());
            long b = Long.parseLong(tk.nextToken());

            System.out.println(lcm(a,b));
        }
    }
    private static long gcd(long a, long b){
        if(b == 0){
            return a;
        }
        else{
            return gcd(b,a%b);
        }
    }
    private static long lcm(long a, long b){
        return (a*b/gcd(a,b));
    }

}

 

5347번: LCM