백준 11688 - 최소공배수 찾기

 

 

문제 설명

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

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

 

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, a, b, L이 주어졌을 때, a, b, c의 최소공배수가 L이 되도록 하는 c의 최솟값을 구해야 한다.

 

우선, 해당 문제를 풀기 위해서는 gcd(최대공약수)와 lcm(최소공배수)을 구하는 방법을 알아야 한다.

gcd는 다음과 같은 간단한 함수로 구할 수 있다.

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

이는 유클리드 호제법으로 구현된 것이다.

https://velog.io/@gjtang/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법

 

gcd를 구했다면 lcm을 구하는 것은 간단하다.

gcd가 두 수의 최대공약수이기 때문에 두 수는 gcd로 나누어 떨어지며, 나누어 떨어진 몫들과 gcd를 곱하면 lcm이 된다.

예를 들어, Y, X가 있고 이 두 수의 gcd를 g라고 하자.

Y와 X를 g로 나눈 몫을 y, x이라 했을 때 lcm은 다음과 같다.

$lcm = y * x * g$

이를 다르게 표현하면, $lcm = (Y/g) * (X/g) * g$이다.

이를 간단히 하면, $lcm = Y * X / g$가 된다.

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

 

c를 구하기 위해서는 다음과 같이 세 개의 수에 대한 식으로 확장해야 한다.

$lcm(a, b) * c = L * gcd(lcm(a, b), c)$

다소 복잡해 보일 수 있지만, 생각해 보면 간단하다.

lcm(a, b)를 Y라 치환하고 c를 X로 치환해 보자.

그럼, 다음과 같은 식이 된다.

$Y * X = L * gcd(Y, X)$

이를 정리해 보면 다음과 같다.

$Y * X / gcd(Y, X) = L$

즉, 앞에서 살펴본 두 수의 lcm을 구하는 식과 동일하다.

 

하지만, 문제는 c를 특정하지 못했다는 것이다.

즉, c가 될 수 있는 후보는 많이 있지만 그중 가장 작은 값을 골라야 한다는 뜻이다.

c가 될 수 있는 후보는 lcm(a, b)와 서로소가 아닌 수가 된다.

lcm(a, b)와 c는 최대공약수를 가져야 L이 될 수 있기 때문이다.

 

정리하자면, lcm(a, b)를 나누었을 때 나누어 떨어지는 수는 c와의 최대공약수 후보가 되며 이를 x라 했을 때, c는 L을 lcm(a, b)로 나눈 수에 x를 곱한 값이 된다.

$c = L / lcm(a, b) *  x$

이때, x가 gcd(lcm(a, b), c)과 같다면 c는 조건을 만족하는 수가 된다.

따라서, lcm(a, b)와 나누어 떨어지는 수 중 조건을 만족하는 x의 최솟값을 찾아 L / lcm(a, b)에 곱하면 c를 찾을 수 있다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

long long a, b, c, L;

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

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;

    cin >> a >> b >> L;

    long long lcmAB = lcm(a, b);

    if (L % lcmAB != 0)
    {
        cout << "-1" << "\n";
        return 0;
    }

    long long k = L / lcmAB;
    
    vector<long long> measures;
    for (long long i = 1; i * i <= lcmAB; i++)
    {
    	if (lcmAB % i == 0)
    	{
            measures.push_back(i);
            measures.push_back(lcmAB / i);
    	}
    }
    
    sort(measures.begin(), measures.end());
    
    bool isFound = false;
    for (int i = 0; i < measures.size(); i++)
    {
    	c = k * measures[i];
    	if (measures[i] == gcd(lcmAB, c))
    	{
            isFound = true;
            break;
    	}
    }
    
    if (isFound == false) c = -1;
    
    cout << c << "\n";
    
    return 0;
}

---