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

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

2436번: 공약수

<풀이>

1. 최대공약수 최소공배수를 입력받고, 최소공배수를 최대공약수로 나눈 숫자를 구한다.

2. 그 숫자들의 약수 짝(두 약수를 곱해서 다시 그 숫자가 되는 두 수)을 구한다.

3. 약수 짝이 서로소인 것을 구한다.

4. 약수 짝(두 수)에 각각 최대공약수를 곱하면, 정답이 가능한 두 수가 된다.

5. 가능한 두 수 중 합이 가장 작은 것을 출력한다.

#include <iostream>
#include <cmath>
using namespace std;
 
long long int gcd, lcm, tmp;
long long int resA = 0, resB = 0;
 
int main() {
 
    //입력
    cin >> gcd >> lcm;
 
    //tmp = 최소공배수 / 최대공약수
    tmp = lcm / gcd;
 
    //tmp의 약수 두 수 구하고, 서로소인지 판별
    for (long long int i = 1; i * i <= tmp; i++) {
        if (tmp % i == 0) {
            //약수 두 수
            long long int tmpA = i;
            long long int tmpB = tmp / i;
 
            //약수 두 수가 서로소인지 판별
            bool isAble = true;
            long long int cnt = 0;
            for (long long int j = 1; j <= tmpA; j++) {
                if (tmpA % j == 0 && tmpB % j == 0) {
                    cnt++;
                }
                //약수의 개수가 1개보다 많은 경우 불가능
                if (cnt > 1) {
                    isAble = false;
                    break;
                }
            }
 
            //가능한 경우 중 가장 마지막에 저장되는 값이 합이 가장 작게된다
            if (isAble) {
                resA = tmpA * gcd;
                resB = tmpB * gcd;
            }
        }
    }
 
    //출력
    cout << resA << " " << resB << "\n";
}

 

최대공약수, 최소공배수에 대해 알아볼 수 있는 문제였습니다.