[Gold V] 공약수 - 2436
성능 요약
메모리: 12872 KB, 시간: 108 ms
분류
브루트포스 알고리즘(bruteforcing), 유클리드 호제법(euclidean), 수학(math), 정수론(number_theory)
문제 설명
어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다.
예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다.
이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다.
예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 예에서와 같이 12와 90일 수도 있으며, 30과 36, 18과 60, 혹은 6과 180일 수도 있다. 그러나, 최대공약수가 6이며 최소공배수가 20인 두 자연수는 있을 수 없다.
두 개의 자연수가 주어졌을 때, 이 두 수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,000,000 이하이다.
출력
첫째 줄에는 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 크기가 작은 수부터 하나의 공백을 사이에 두고 출력한다. 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수 쌍이 여러 개 있는 경우에는 두 자연수의 합이 최소가 되는 두 수를 출력한다.
풀이
최대공약수 A와 최소공배수 B를 곱한 A*B는, A를 최대공약수, B를 최소공배수로 가진 두 수의 곱과 같다.
즉 A*B의 약수인 두 수 중 최대공약수가 A인 경우를 찾으면 된다.
A*B의 모든 약수를 탐색하지 않고 최대공약수 A의 배수들 중에서 답을 찾으려고 했다.
for문에서 탐색할 때 i의 제곱이 A*B보다 작을때까지만 탐색해서 중복을 제거하였다.
또한 두 수의 합이 가장 작은 경우는 두 수의 차가 가장 작은 경우이기 때문에 마지막에 찾은 값으로 업데이트해준다.
package BOJ.Gold.g5;
import java.util.Scanner;
public class BOJ_2436_공약수 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long A = sc.nextLong();
long B = sc.nextLong();
long mul = A * B;
long[] ans = new long[2];
// A*B의 약수이면서 A의 배수인 수 찾기
for (long i = A; i * i <= mul; i += A) {
// A의 배수들
// i랑 mul/i의 최소공약수가 A라면 답으로 업데이트
if (mul % i == 0) { // i가 mul의 약수
long num1 = i;
long num2 = mul / i;
while (num1 > 0) {
long tmp = num2 % num1;
num2 = num1;
num1 = tmp;
}
if (num2 == A) {
ans[0] = i;
ans[1] = mul / i;
}
}
}
System.out.println(ans[0] + " " + ans[1]);
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 6087 - 레이저 통신 (자바 Java) (0) | 2022.12.19 |
---|---|
[백준] 7570 - 줄 세우기 (자바 Java) (0) | 2022.12.14 |
[백준] 7569 - 토마토 (자바 Java) (0) | 2022.12.12 |
[백준] 14891 - 톱니바퀴 (자바 Java) (0) | 2022.12.11 |
[백준] 1107 - 리모컨 (자바 Java) (0) | 2022.12.04 |