[백준 2436] 공약수 (C++)

https://www.acmicpc.net/problem/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 이하이다.

 

출력

---

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

 

문제 풀이

---

유클리드 호제법을 이용한 문제.

어떤 수 a와 b의 최소공배수 lcm이 존재한다면 a와 b는 lcm의 약수이다. lcm의 모든 약수를 구해 벡터에 넣어준다.

이중 반복문을 이용해 두 개의 자연수를 선택하여 최대공약수와 최소공배수를 구한다. 

a와 b의 최대공약수는 b와 a%b의 최대 공약수와 같다는 것을 이용하면 빠르게 최대공약수를 구할 수 있으며, 최대 공약수 gcd * 최소공배수 lcm = a* b라는 성질을 이용하면 최소공배수를 구할 수 있다. 최대 공약수와 최소공배수가 둘다 입력받은 값과 동일하다면 이에 해당하는 a와 b가 정답이다.

두 자연수는 서로 다르다는 조건이 없으므로 두 자연수가 동일할 수 있음에 주의해야 하며, 이때 최대공약수와 최소공배수는 같다.

 

아래는 코드.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;


int GCD(int x, int y)
{
	if (y == 0)
	{
		return x;
	}
	else
	{
		return GCD(y, x % y);
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	long long N, M;
	long long answerA = 100000000;
	long long answerB = 100000000;
	cin >> N >> M;
	vector<long long> v;
	for (int i = 1; i <= sqrt(M); i++)
	{
		if (M % i == 0)
		{
			if (M / i != i)
			{
				v.push_back(M / i);
			}
			v.push_back(i);
		}
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++)
	{
		for (int j = i ; j < v.size(); j++)
		{
			long long gcd = GCD(v.at(j), v.at(i));
			long long lcm = (long long) v.at(j) * (long long) v.at(i) / gcd;
			if (gcd == N && lcm == M && v.at(j) + v.at(i) < answerA + answerB)
			{
				answerA = v.at(i);
				answerB = v.at(j);
			}
		}
	}
	cout << answerA << " " << answerB << "\n";
	return 0;
}