문제
두 자연수의 최대공약수와 최소공배수가 주어졌을 때, 합이 최소인 두 자연수를 구하라.
입력
첫째 줄에 최대공약수와 최소공배수가 주어진다.
출력
합이 최소인 두 자연수를 공백으로 구분하여 출력한다.
예제
| 입력 | 출력 |
|---|---|
6 180 | 30 36 |
풀이
GCD × LCM = A × B 성질을 이용하여 가능한 쌍을 탐색한다.
A * B = GCD * LCM이므로 곱mul을 구한다- GCD의 배수인 i를 GCD부터
sqrt(mul)까지 순회한다 mul % i == 0이고gcd(i, mul/i) == GCD인 쌍을 찾는다- 여러 쌍 중
sqrt(mul)에 가장 가까운 쌍이 합이 최소이므로, 마지막으로 갱신된 값이 답이다
핵심 아이디어: 곱이 고정된 두 수의 합은 두 수가 가까울수록 최소이다. GCD 배수만 탐색하고, GCD 조건을 확인하여 유효한 쌍만 선택한다.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day343BOJ2436공약수 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int gcd = Integer.parseInt(st.nextToken());
int lcd = Integer.parseInt(st.nextToken());
long mul = (long) gcd * lcd;
int a = 0, b = 0;
for (int i = gcd; i <= Math.sqrt(mul); i += gcd) {
if (mul % i == 0 && euclidean(i, mul / i) == gcd) {
a = i;
b = (int) (mul / i);
}
}
System.out.println(a + " " + b);
}
public static long euclidean(long a, long b) {
long r = a % b;
if (r == 0)
return b;
return euclidean(b, r);
}
}복잡도
- 시간: O(sqrt(GCD * LCM) / GCD * log(max)) - 배수 탐색 × GCD 계산
- 공간: O(1)