[백준 11688] 최소공배수 찾기 (C++)

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

11688번: 최소공배수 찾기

 

문제

---

세 정수 a, b, L이 주어졌을 때, LCM(a, b, c) = L을 만족하는 가장 작은 c를 찾는 프로그램을 작성하시오. LCM(a, b, c)는 a, b, c의 최소공배수이다.

 

입력

---

첫째 줄에 a, b, L이 주어진다. (1 ≤ a, b ≤ 10⁶, 1 ≤ L ≤ 10¹²)

 

출력

---

첫째 줄에 c를 출력한다. 만약, 가능한 c가 없으면 -1을 출력한다.

 

 

문제 풀이

---

제목 그대로 최소공배수를 찾는 문제.

어떤 두 수를 각각 a,b라 하면 a * b = GCD(최대공약수) * LCM(최소공배수)인 것을 이용해 답을 구하는 문제이다.

a,b의 최소공배수(alpha)를 구하면, alpha와 c의 최대공배수가 L이 된다.

따라서 alpha * c = L * GCD(alpha, c)가 성립한다. 모든 수는 정수이므로 L이 alpha로 나누어떨어져야한다. 나누어떨어지지 않는다면 만족하는 c가 없으므로 -1을 출력한다.

위의 식을 다시 쓰면 c= (L/alpha) * GCD(alpha, c)이다. 반복문을 돌리며 alpha의 약수를 구하고 해당 약수가 최대공약수라 가정한 후 (L/alpha)를 곱하면 c를 구할 수 있다. c와 alpha의 실제 최대공약수를 구했을 때 우리가 최대공약수라 가정한 그 약수라면 식이 성립하므로 해당 c가 정답이다.

 

아래는 코드.

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

long long gcd(long long x, long long y)
{
	if (y == 0)
	{
		return x;
	}
	else
	{
		return gcd(y, x % y);
	}
}

long long lcm(long long x, long long y)
{
	return x * y / gcd(x, y);
}

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

	long long a, b, L;
	cin >> a >> b >> L;
	long long alpha = lcm(a, b);
	long long k = L / alpha;
	long long c = -1;
	if (L % alpha != 0)
	{
		cout << "-1" << "\n";
	}
	else
	{
		vector<long long> v;
		for (long long i = 1; i <= sqrt(alpha); i++)
		{
			if (alpha % i == 0)
			{
				v.push_back(i);
				v.push_back(alpha / i);
			}
		}
		sort(v.begin(), v.end());
		bool isFound = false;
		for (int i = 0; i < v.size(); i++)
		{
			c = k * v.at(i);
			long long gcdAlphaC = gcd(alpha, c);
			if (gcdAlphaC == v.at(i))
			{
				isFound = true;
				break;
			}
		}
		if (isFound == false)
		{
			cout << "-1" << "\n";
		}
		else
		{
			cout << c << "\n";
		}
	}
	return 0;
}