[백준] 1934 : 최소공배수 JAVA 풀이

 

바로 이전에 올렸던 2609번을 푼 사람이라면 아주 쉽게 풀 수 있는 문제다.

 

핵심은 이것

 

숫자 A와 B가 있고, r을 A % B라고 했을 때 ( A >= B )

최대공약수 GCD(A,B) = GCD(B,r)

그리고 A = ad, B = bd (a와 b는 서로소이고, d는 A와 B의 최대공약수)라고 했을 때

A와 B의 최소공배수는 abd이다.

따라서 A와 B가 주어지고 둘의 최대공약수인 d를 구한다면

AB = adbd 이니 이것을 d로 나눠주면 최소공배수를 구할 수 있다.

 

 

import java.io.*;
import java.util.*;
 
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int d = gcd(A,B);
            System.out.println(A*B/d);
        }
    }
    
    public static int gcd(int a, int b){
        while(b!=0){
            int r = a % b;
            
            a = b;
            b = r;
        }
        return a;
    }
}