문제
두 자연수 A, B의 최소공배수를 구하라.
입력
첫째 줄에 테스트 케이스 수 T, 이후 T줄에 A, B가 주어진다.
출력
각 테스트 케이스에 대해 최소공배수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 1 45000 6 10 13 17 | 45000 30 221 |
풀이
유클리드 호제법으로 GCD를 구한 뒤, LCM = A * B / GCD로 최소공배수를 계산한다.
- 반복문으로 유클리드 호제법을 구현한다:
a % b를 b가 0이 될 때까지 반복 a * b / gcd(a, b)로 LCM을 구한다
핵심 아이디어: GCD(A, B) * LCM(A, B) = A * B 성질을 이용한다. 유클리드 호제법은 O(log(min(A, B)))에 GCD를 구한다.
코드
package day399;
import java.io.*;
import java.util.*;
public class Day385BOJ1934최소공배수 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
StringTokenizer st;
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int d = gcd(a, b);
sb.append(a * b / d).append('\n');
}
System.out.println(sb);
}
public static int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
}복잡도
- 시간: O(T * log(min(A, B))) - 각 쌍마다 유클리드 호제법
- 공간: O(1)