[BOJ] 백준 2436번 공약수 (Java)

#2436 공약수

난이도 : 골드 5

유형 : 정수론 / 유클리드 호제법 

2436번: 공약수

▸ 문제

어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다.

예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다.

이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다. 

예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 예에서와 같이 12와 90일 수도 있으며, 30과 36, 18과 60, 혹은 6과 180일 수도 있다. 그러나, 최대공약수가 6이며 최소공배수가 20인 두 자연수는 있을 수 없다.

두 개의 자연수가 주어졌을 때, 이 두 수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 구하는 프로그램을 작성하시오. 

▸ 입력

첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,000,000 이하이다.

▸ 출력

첫째 줄에는 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 크기가 작은 수부터 하나의 공백을 사이에 두고 출력한다. 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수 쌍이 여러 개 있는 경우에는 두 자연수의 합이 최소가 되는 두 수를 출력한다.

 

문제 풀이  

최대공약수(gcd) 6, 최소공배수(lcm) 180이 있을 때 gcm*lcd의 약수로 되어있는 자연수의 쌍이 해당 gcm과 lcd를 가지는 것을 알 수 있다.

• 예를들어, gcd*lcm = 720 이라고 하면 (x, y) = (2, 190), (3, 240), ... (12, 90), (24, 45), (30, 36), ... 가 될 수 있다. 
• 우리는 이 쌍 중에서 gcd를 최대공약수로 가지고 lcm을 최소공배수로 가지는 쌍을 구해주면 된다. (2, 190)의 gcd는 2이므로 탈락, (3, 240)은 3이므로 탈락 ...

 

이 쌍을 쉽게 구하는 법이 있다.  lcm을 gcd로 나눈 값으로 서로소로 이루어진 쌍을 구해 gcd를 곱해 구해주는 것이다. 위의 값을 예시로 들면 lcm/gcd = 30이다. 30의 약수는 (1, 30), (2, 15), (3, 10), (5, 6) 와 같다. 이 중에서 서로소로 이루어져 있는 쌍들을 gcd에 곱하면 (6, 180), (12, 90), (18, 60), (30, 36)이 나옴을 알 수 있고 이 수들은 기존 gcd와 lcm이 일치함을 알 수 있다.

• 만약 서로소 이루어져있지 않은 쌍을 곱하면 gcd의 값은 변하게 된다. 예를들어 gcd = 6, lcm =144라고 할 때 (2, 12)의 쌍을 곱하면 (12, 72)로 gcd의 값이 12로 변했음을 볼 수 있다.

 

따라서 유클리드 호제법을 사용하여 gcd의 값이 1인 쌍을 구하여 가장 나중에 구해지는 쌍(합이 최소인 쌍)을 입력받아 출력하면 된다.

 

풀이 코드 

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int gcd = Integer.parseInt(st.nextToken());
		int lcm = Integer.parseInt(st.nextToken());
		
		int tmp = lcm/gcd;
		
		long resA = 0, resB =0;
		for(int i=1; i*i<=tmp; i++) {
			if(tmp%i==0) {
				int aa = i;
				int bb = tmp/i;
				if(getGCD(aa,bb)==1) {
					resA = aa*gcd;
					resB = bb*gcd;
				}
			}
		}
		System.out.println(resA+" "+resB);
	}
	
	static int getGCD(int a, int b) {
		return a%b == 0 ? b: getGCD(b, a%b);
	}
}