백준2436 - 공약수

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

2436번: 공약수

최대공약수와 최소공배수가 주어진다. 주어진 최대공약수를 가지는 수들 중에서 주어진 최소공배수를 만족하는 경우의 수들 중 합이 최소가 되는 수를 찾으면 된다. 단순히 약수를 분류하고 가장 중간에 위치한 약수를 답으로 선택하면 안된다. 왜냐하면 주어진 최소공배수에서 수를 분리하는 과정에서 서로 다른 두 개의 약수가 최대 공약수 외에 같은 약수를  포함할 수 있기 때문이다. 그렇기 때문에 약수 찾기를 하는 도중에 최대공약수를 구하는 유클리드 호제법을 이용하여 서로소가 되는 수를 찾는다. for문이 반복하면서 서로소가 되는 수들 중 합이 작은 수가 있으면 자동으로 갱신한다.

 

#include <iostream>
using namespace std;

//최대공약수 구하기, 재귀 호출 사용
int gcd(int x, int y) {
	if (y == 0) {
		return x;
	}
	else {
		return gcd(y, x % y);
	}
}

int main() {
	int a, b; //a는 최대 공약수, b는 최소 공배수
	int x; //서로소가 되어질 약수의 원소
	long long int res1 = 1, res2 = 1; //결과

	cin >> a >> b;

	b = b / a; //최대 공약수를 최소 공배수로 한 번 나누어 탐색 횟수를 줄인다.

	//약수 찾기
	for (int i = 1; i * i <= b; i++) {
		//약수를 찾고 약수와 상대 관계에 있는 약수(곱하면 b가 나오는 i, b/i)가 서로소 관계애 있는지 확인한다.
		if (b % i == 0 && gcd(i, b / i) == 1) { 
			x = i;
		}
	}
	
	//res1과 res2를 구한다.
	res1 = a * x;
	res2 = a * (b / x);

	cout << res1 << ' ' << res2;
}