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

문제

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

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

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

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

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

 

입력

첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,000,000 이하이다.

 

출력

첫째 줄에는 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 크기가 작은 수부터 하나의 공백을 사이에 두고 출력한다. 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수 쌍이 여러 개 있는 경우에는 두 자연수의 합이 최소가 되는 두 수를 출력한다.

---

역시나 접근이 까다로웠던 문제...ㅜㅜ 처음에 유클리드호제법을 이용해서 나름의 풀이로 구해보려 했는데, 그랬더니 안맞는 조건들이 생기면서 답이 안나와서 어렵게 풀었다ㅠㅠ

최대공약수와 최대공배수를 먼저 입력받은 뒤, 이를 나눠준 것의 약수를 구한다. 약수들 가운데 서로소인 한 쌍에 다시 최대공약수만큼을 곱해준 값이 답이 된다.

 

코드

#include <cstdio>
#include <cmath>

int main(void) {
    int a, b;
    scanf("%d %d", &a, &b);
    
    long long int div = b / a;

    long long int num1 = 0, num2 = 0;
    
    for(long long int i = 1; i * i <= div; i++) {
        if(div % i == 0) {
            long long int temp1 = i;
            long long int temp2 = div / i;

            bool flag = true;
            int count = 0;
            for(int i = 1; i <= temp1; i++) {
                if(temp1 % i == 0 && temp2 % i == 0) count++;

                if(count > 1) {
                    flag = false;
                    break;
                }
            }

            if(flag) {
                num1 = temp1;
                num2 = temp2;
            }
        }
    }

    printf("%lld %lld\n", num1 * a, num2 * a);
    return 0;
}