[BOJ] 2436 : 공약수 - travelbeeee

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

---

[ 알고리즘풀이 ]

 임의의 두 수 x, y에 대해서  최대공약수[gcd(x,y)] * 최소공배수[lcm(x,y)] = x * y 인 정리와 수학적 정의에 의해 임의의 두 수 x, y는 모두 최대공약수의 배수인 사실을 이용해 문제를 해결할 수 있습니다.

 

1. 최대공약수(A)와 최소 공배수(B)가 주어지면 두 수를 곱해 C를 구합니다.

2. 최대공약수(A)의 배수 중 C의 약수인 수를 i라고 한다면, i 와 C / i 쌍을 얻을 수 있습니다.

3. i 와 C / i 쌍이 최대공약수가 A라면 이 둘은 우리가 원하는 쌍이고 현재 찾아놓은 쌍과 비교해서 합이 더 작다면 값을 갱신합니다.

#include<iostream>

using namespace std;

long long gcd(long long a, long long b) {
	while (a) {
		long long r = b % a;
		b = a;
		a = r;
	}
	return b;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	long long A, B, C, ans1, ans2;
	cin >> A >> B;
	C = A * B, ans1 = A, ans2 = B;
	for (long long i = 2 * A; i * i <= C; i += A) {
		if(C % i == 0){
			long long temp = C / i;
			if (gcd(i, temp) == A) {
				if (ans1 + ans2 > i + temp) {
					ans1 = i, ans2 = temp;
				}
			}
		}
	}
	cout << ans1 << ' ' << ans2;
	return 0;
}

주의해야할 점은 A와 B 값을 곱하는 과정에서 int형 범위를 벗어날 수 있다는 점입니다.

---