백준 2436 - 공약수

문제 설명

어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다. 

예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다.

이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다. 

예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 예에서와 같이 12와 90일 수도 있으며, 30과 36, 18과 60, 혹은 6과 180일 수도 있다. 그러나, 최대공약수가 6이며 최소공배수가 20인 두 자연수는 있을 수 없다.

두 개의 자연수가 주어졌을 때, 이 두 수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 구하는 프로그램을 작성하시오. 

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 전달받은 A, B를 각각 최대 공약수, 최소 공배수로 하는 수의 쌍을 구하는 것이다.

수의 쌍이 많을 경우 두 수의 합이 가장 작은 수의 쌍을 출력하면 된다.

 

해당 문제는 수학적인 개념을 적용하면 간단하게 풀 수 있다.

우리가 구해야 하는 두 수를 X, Y라고 해보자.

최대 공약수는 X, Y에 모두 포함되어 있는 가장 큰 약수이다.

최대 공약수를 A, 최소 공배수를 B라고 한다면 X = A * x, Y = A * y가 되는 것이다.

최소 공배수 B는 다음과 같이 표현할 수 있다.

B = A * x * y

즉, 우리는 x와 y만 구하면 되는 것이다.

그럼 x와 y를 구하는 방법은 어떻게 될까?

B를 A로 나눈다면 x * y를 구할 수 있다.

이를 K라고 한다면 K의 약수로 x, y의 쌍을 고를 수 있다.

예를 들어, K가 12라고 한다면 약수는 {1, 2, 3, 4, 6, 12}이다.

이중 곱이 K가 되는 두 수를 뽑고 그 합이 가장 작게 만들면 된다.

합이 가장 작게 만들려면 최대한 가운데 있는 수를 뽑는 게 유리하다.

(3, 4)와 (2, 6) 모두 뽑을 수 있지만 그 합은 7과 8로 (3, 4)가 정답이 된다.

단, 여기서 주의할 점은 (2, 6)처럼 뽑은 쌍이 공약수를 갖는 경우가 있다.

지금의 경우 2를 공약수로 갖는다.

이렇게 되면 최대 공약수에 2가 곱해지기 때문에 최대 공약수에 대한 조건이 맞지 않게 된다.

또한, K의 약수의 개수가 홀수개라면 K는 제곱수임을 뜻하며 이러한 경우에는 K의 제곱근을 두 번 고르는 것이 최적해가 된다.

 

정리하자면, B를 A로 나눈 수 K에 약수를 구해 제곱수라면 제곱근을 선택하고 그렇지 않다면 가운데서부터 공약수가 추가로 존재하지 않는 숫자 쌍 (x, y)를 고르면 된다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int A, B;


int main() 
{
    INPUT_OPTIMIZE;

    cin >> A >> B;

    int k = B / A;

    vector<int> nums;

    //k의 약수 구하기
    for (int i = 1; i * i <= k; i++)
    {
        if (k % i == 0)
        {
            nums.push_back(i);
            if (i * i != k)
            {
                nums.push_back(k / i);
            }
        }
    }

    sort(nums.begin(), nums.end());

    int x;
    int y;
    if (nums.size() % 2 == 1)
    {
        int mult = nums[nums.size() / 2];

        x = A * mult;
        y = A * mult;
    }
    else
    {
        int left = nums.size() / 2 - 1;
        int right = nums.size() / 2;

        while (true)
        {
            int leftNum = nums[left];
            int rightNum = nums[right];

            bool hasSame = false;
            for (int i = 2; i * i <= leftNum; i++)
            {
                if (leftNum % i == 0 && rightNum % i == 0)
                {
                    hasSame = true;
                    break;
                }
            }

            if (!hasSame) break;
            left--;
            right++;
        }

        x = A * nums[left];
        y = A * nums[right];
    }

    cout << x << " " << y;

    return 0;
}

---