[Java] 백준 / 공약수 / 2436번

[Java] 백준 / 공약수 / 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 이하이다.

6 180

출력

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

30 36

접근 방식

1. a와 b 의 최대 공약수와 최소 공배수 곱은 ab 와 같다. 따라서 최대 공약수와 최소 공배수의 곱을 변수 mul로 둔다. 이 때 a와 b는 최대 1억이기 때문에 ab인 mul은 long 타입으로 선언한다
2. 반복문으로 최대 공약수의 배수를 탐색한다
3. 최대 공약수의 배수인 i를 subA라 두고 mul % subA가 0으로 나누어 떨어지는지 확인한다
4. 나누어 떨어진다면 mul / subA 를 subB로 두고 subA와 subB의 최대공약수를 유클리드 호제법으로 확인하여 입력받은 최대공약수와 일치한다면 구하려는 a 와 b 의 후보가 된다

코드

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

public class Main_G5_2436 {

	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 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);
	}
	
	
	// a와 b의 최대 공약수는 b와 a%b의 최대 공약수와 같다 (유클리드 호제법)
	public static long euclidean(long a, long b) {
		long r = a % b;
		if( r == 0) {
			return b;
		}
		return euclidean(b,r);
	}

}