백준 2436 - 공약수 (C++)

 

 

일반적인 공약수를 구하는 문제를 반대로 제시한 문제이다.

 

A와 B가 주어졌을 때 GCD와 LCM을 구하는 것이 아니라, GCD와 LCM이 주어졌을 때 A와 B를 구하는 문제이다.

물론, A와 B의 쌍은 여럿 존재할 수 있기 때문에 그 중에서 A와 B의 합이 최소인 쌍을 출력해주면 된다.

 

문제 풀이

 

먼저, 두 수 A,B에 최대 공약수를 G, 최소공배수를 L이라고 한다면 A와 B는 반드시 GCD의 배수이다.

 

이를 이용하여, L보다 작은 G의 배수를 모두 구한 뒤, 그 중 2개를 뽑아 두 수의 최소 공배수와 최대 공약수가  G, L과 동일한지를 검사하여 조건을 만족하는 (A, B)쌍을 모두 구할 수 있을 것이다.

 

하지만, 문제의 조건을 보면 숫자의 범위가 2~100,000,000이다.

위와 같은 방식으로 답을 구하려고 했다간 시간초과가 발생할 수 밖에 없다.

 

그렇기 때문에, 위에서 주어진 풀이 방법을 기반으로 범위를 좁히는 것이 필요하다.

두 수를 구하기 위해 과연 G보다 작은 L의 배수를 모두 구해야 할까?

 

먼저 한 가지 수식을 보자.

 

$$GCD = \frac{A * B}{LCM}$$

 

유클리드 호제법에 따르면, 위 공식이 성립한다.

여기서 변환을 하나 해보자.

 

$$GCD * LCM = A * B$$

 

이렇게도 표현할 수 있을 것이다.

 

A와 B의 곱이 GCD * LCM 이라고 한다면, A와 B 둘 중 하나는 반드시 GCD * LCM의 제곱근보다 작거나 같아야 한다.

M = A * B 이고, R을 M의 제곱근이라고 했을 때, 4가지 경우

 

1.  A = R 인 경우

=> R * B = R * R 이므로, B또한 R이다.

=> A = R, B = R

 

2. A > R 인 경우

=> B또한 R보다 크다면, A * B는 (R + a) * (R + b)이 되므로, R * R 보다 큰 값을 가지게 됨. (a, b는 양의 정수)

A * B = R * R 을 만족하려면, B는 R보다 작아야 함.

 

3.A < R 인 경우

=> 위 조건과 마찬가지의 논리로, B가 R보다 커야함.

 

그러므로, A와 B중 하나는 반드시 R보다 작거나 같아야 한다.

즉, LCM보다 작은 GCD의 배수를 모두 구하는 것이 아니라, GCD * LCM의 제곱근보다 작은 GCD의 배수에서만 값을 구하면 된다.

 

또한, GCD * LCD = A * B 이므로, A를 결정하였다면, GCD * LCD를 A로 나눠서 바로 B를 구할 수도 있기 때문에, GCD의 배수를 모두 구할 필요가 없게 된다.

 

풀이 코드

long long GCD = 0;
long long LCM = 0;

std::cin >> GCD >> LCM;

GCD와 LCM을 입력받았다.

long long Mul = GCD * LCM;
long long MulSqrt = std::sqrt(Mul);

두 수의 곱의 제곱근도 구해주었다.

long long MinSum = LLONG_MAX;
std::pair<int, int> Answer;

for (int i = GCD; i <= MulSqrt; i += GCD)
{
    long long  Cur = i;
    long long  Other = Mul / Cur;

    int  CurGCD = GetGCD(Cur, Other);
    long long  CurLCM = Cur * Other / CurGCD;

    if (CurGCD == GCD && CurLCM == LCM)
    {
        if (Cur + Other < MinSum)
        {
            MinSum = Cur + Other;
            Answer = { Cur, Other };
        }
    }
}

이후, 반복문을 돌며 위에서 말한 논리로 두 숫자 쌍을 구해주었다.

GCD의 배수에 대해서만 검사를 하도록 하였으며, 숫자 1개를 구했다면 GCD * LCM을 해당 숫자로 나누어 다른 숫자도 구해주었다.

 

그리고 두 숫자의 최소 공배수와 최대 공약수가 입력받은 값과 동일한지를 검사하여 조건을 만족하는 두 숫자인지 검사한 뒤, 두 수의 합을 기준으로 Answer를 갱신해주었다.

long long GetGCD(int _Left, int _Right)
{
	int Remain = _Left % _Right;

	while (Remain > 0)
	{
		Remain = _Left % _Right;
		_Left = _Right;
		_Right = Remain;
	}

	return _Left;
}

최대 공약수는 위와 같이 유클리드 호제법으로 구해주었다.

std::cout << Answer.first << " " << Answer.second;

return 0;

마지막에 답을 출력해주면 끝이다.

 

코드 전문

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
#include <cmath>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

long long GetGCD(int _Left, int _Right)
{
    int Remain = _Left % _Right;

    while (Remain > 0)
    {
        Remain = _Left % _Right;
        _Left = _Right;
        _Right = Remain;
    }

    return _Left;
}

int main()
{
    Init();

    long long GCD = 0;
    long long LCM = 0;

    std::cin >> GCD >> LCM;

    long long Mul = GCD * LCM;
    long long MulSqrt = std::sqrt(Mul);

    long long MinSum = LLONG_MAX;
    std::pair<int, int> Answer;

    for (int i = GCD; i <= MulSqrt; i += GCD)
    {
        long long  Cur = i;
        long long  Other = Mul / Cur;

        int  CurGCD = GetGCD(Cur, Other);
        long long  CurLCM = Cur * Other / CurGCD;

        if (CurGCD == GCD && CurLCM == LCM)
        {
            if (Cur + Other < MinSum)
            {
                MinSum = Cur + Other;
                Answer = { Cur, Other };
            }
        }
    }

    std::cout << Answer.first << " " << Answer.second;
    	
    return 0;
}