[BaekJoon] 2436 공약수

1.  문제 링크

https://www.acmicpc.net/problem/2436

2.  문제

요약

• 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있습니다.
• 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수도 있으며 없을 수도 있습니다.
• 두 개의 자연수가 주어졌을 때, 이 두 수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 2 이상 100,000,000 이하인 두 개의 자연수가 주어지는데 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고 두 번째 수는 그 자연수들의 최소공배수를 뜻합니다.
• 출력: 첫 번째 줄에 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 크기가 작은 수부터 출력합니다. 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수 쌍이 여러 개라면 두 자연수의 합이 최소가 되는 두 수를 출력합니다.

3.  소스코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int A, B;
	static long n1, n2;
	
	static void input() {
		Reader scan = new Reader();
		A = scan.nextInt();
		B = scan.nextInt();
	}
	
	static void solution() {
		n1 = (long)A;
		n2 = (long)B;
		long multiply_n = n1 * n2; // gcd(n1, n2) * lcm(n1, n2) = n1 * n2
		for(long i = 2 * (long)A; i * i <= multiply_n; i += A) {
			if(multiply_n % i == 0) {
				long temp = multiply_n / i;
				if(gcd(i, temp) == A) {
					if(n1 + n2 > i + temp) {
						n1 = i;
						n2 = temp;
					}
				}
			}
		}
		sb.append(n1 + " " + n2 + "\n");
	}
	
	static long gcd(long i, long temp) {
		return temp == 0 ? i : gcd(temp, i % temp);
	}
	
	public static void main(String[] args) {
		input();
		solution();
		System.out.println(sb.toString());
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• 임의의 두 수 n1, n2에 대해서 최대공약수×최대공배수$(gcd(n_1, n_2)×lcm(n_1, n_2)) = n_1×n_2$가 성립합니다.
• 그렇기 때문에 우리는 이 문제를 $n_1×n_2$의 약수이면서, 최대공약수의 배수인 두 수를 찾으면 되는 문제로 생각할 수 있습니다.
• 아래와 같은 과정으로 문제를 해결합니다.

1. 주어진 A를 최대공약수로, B를 최소공배수로 하는 두 수를 나타내는 변수 $n_1$, $n_2$를 생성하고 초기값은 $n_1$은 최대공약수로, $n_2$는 최소공배수로 초기화합니다.
2. 최대공약수와 최소공배수를 곱하여 $n_1×n_2$을 구합니다.
3. $n_1×n_2$의 약수이면서, 최대공약수의 배수인 두 수를 찾는데 초기값을 최대공약수와 최소공배수로 하였기 때문에 최대공약수가 두 수 중 하나일 때는 확인할 필요가 없고 두 수 중 하나가 최대공약수 * 2일 때부터 제곱을 했을 때 2번에서 구한 수일 때까지 최대공약수만큼 더해가며 해당 수가 조건에 맞는 두 수 중 하나가 될 수 있는지 확인합니다.
   1. 만약 $n_1×n_2$가 현재 수로 나누어떨어지지 않는다면 $n_1×n_2$의 약수가 아니므로 현재 수는 두 수 중 하나가 될 수 없기에 다음 수로 넘어갑니다.
   2. $n_1×n_2$를 현재 수로 나누어 나온 수가 현재 수가 두 수 중 하나일 때 나머지 수가 되기 때문에 $n_1×n_2$를 현재 수로 나누어 해당 수를 temp에 저장합니다.
   3. 현재 수와 temp와의 최대공약수를 구해서 만약 구한 최대공약수가 주어진 A가 된다면 이 두 수는 우리가 찾는 두 수가 될 수 있습니다.
   4. 이 두 수의 합을 이전에 찾아놓은 $n_1$, $n_2$ 두 수의 합과 비교하여 $n_1$, $n_2$의 합보다 작다면 $n_1$, $n_2$을 현재 두 수로 변경합니다.