jayyhkwon의 개발공부로그

BOJ 1934번 최소공배수

26 Dec 2019 | Algorithm

최대 공약수 (GCD)

  • 두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다.

  • 최대공약수가 1인 두 수를 서로소라고 한다

  1. 2부터 min(A,B)까지 모든 정수로 나눈다
int g =1;
for(int i=2; i<=min(A,B); i++){
  if(a%i == 0 && b % i ==0){
    g=i;
  }
}
  1. 유클리드 호제법
  • A를 B로 나눈 나머지를 r이라 했을때 GCD(A,B) = GCD(B,r)
public void int gcd(int a, int b){
  if(b==0)
    return a;
  else
    return gcd(b,a%b);
}

최소공배수 (LCM)

  • 두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수
  • LCM = (A*B)/GCD
package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * BOJ 1934
 * https://www.acmicpc.net/problem/1934
 * LCD * GCD = A * B
 */
public class LCD_1934 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] answer = new int[n];
        int idx = 0;
        while(n-- > 0){
            int[] numbers = Arrays.asList(br.readLine().split("\\s")).stream().mapToInt(Integer::parseInt).toArray();
            int lcd = (numbers[0] * numbers[1]) / gcd(numbers[0],numbers[1]);
            answer[idx] = lcd;
            idx++;
        }

        for(int num : answer)
            System.out.println(num);


    }

    private static int gcd(int a, int b){
        if(b == 0)
            return a;

        return gcd(b, a%b);

    }


}

Related Posts