[백준][C++] 2436: 공약수

문제

2436번: 공약수

풀이

수학, 유클리드 호제법

 

입력받은 최대공약수를 A, 최소공배수를 B, 구해야 하는 수를 x, y라고 하면 다음이 성립한다.

x % A = 0, y % A = 0

(x * y) / A = B

 

N을 x를 A로 나눈 몫이라고 하면 다음이 성립한다. 

x = N * A

위 식을 (x * y) / A = B에 대입하면 다음의 결과를 얻을 수 있다. 

x = N * A, y = B / N

 

y는 자연수 이므로, B / N은 나누어 떨어져야 한다. 그러므로, N은 B의 약수이다. 즉, B의 약수로 계산한 (x, y)의 최대공약수가 A이면서 최소공배수가 B인 (x, y) 중에서 (x + y)의 값이 최소인 (x, y)를 구하면 된다.

코드

#include <iostream>
#include <vector>

using namespace std;

vector<long long> divisor;

long long gcd(long long a, long long b)
{
    if (a < b)
    {
        swap(a, b);
    }

    long long temp;
    while (b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

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

    int A, B;
    cin >> A >> B;

    // B의 약수를 divisor에 저장
    for (int i = 1; i * i <= B; ++i)
    {
        if (B % i == 0)
        {
            divisor.push_back(i);
            if (B / i != i)
            {
                divisor.push_back(B / i);
            }
        }
    }

    long long answer_x = 150'000'000;
    long long answer_y = 150'000'000;
    for (int i = 0; i < divisor.size(); ++i)
    {
        long long x = divisor[i] * A;
        long long y = B / divisor[i];

        long long GCD = gcd(x, y);
        long long LCM = (x * y) / GCD;

        // (x, y)의 최대공약수가 A이면서, 최소공배수가 B인 (x, y)
        if (GCD == A && LCM == B)
        {
            if (answer_x + answer_y > x + y)
            {
                answer_x = x;
                answer_y = y;
            }
        }
    }

    cout << answer_x << " " << answer_y;

    return 0;
}