[백준 2436번] 공약수 (C++)

문제링크 : https://www.acmicpc.net/problem/2436

2436번: 공약수

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

ll A, B, rA, rB;

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

    cin >> A >> B;

    ll tmp = B/A; //서로소의 곱
    
    for(int i=1; i*i<=tmp; i++) //약수 체크
    {
        if(tmp%i) continue;
        ll a = i, b = tmp/i;
        if(gcd(a, b)==1) //서로소 찾기
        {
            rA = a*A; //서로소 * 최대공약수 (원래 A, B)
            rB = b*A;
        }
    }
    cout << rA << " " << rB;
    return 0;
}

 

A와 B의 최소공배수는 A와 B의 최대공약수 * A/최대공약수 * B/최대공약수이다.

(LCM = GCD * A/GCD * B/GCD)

여기서 추가로 알 수 있는 것은 LCM/GCD = A/GCD * B/GCD라는 것이다.

 

A/GCD와 B/GCD는 다음과 같이 서로 서로소인 것을 알 수 있다.

최대공약수 : 6, 최소공배수 : 180

6 30 36
   5  6
   
최대 공약수로 나눠서 나온 값 5, 6은 서로 서로소

 

여기서 우리는 두 자연수가 서로 서로소인 것과, 두 자연수의 곱이 몇인지만 알고 있다.

따라서 두 자연수의 곱의 약수를 구하여 해당 약수 2개 끼리 서로 서로소인지 체크를 위해 최대공약수가 1인지 확인한다.

우리가 찾는 것은 조건을 만족하는 두 자연수의 합 중 가장 작은 값을 원하므로, 두 자연수의 갭이 가장 작아지는 맨 마지막에 조건을 만족하는 쌍을 구해준다.

최대공약수 : 6, 최소공배수 : 180

180/6 = 30
30의 약수 (1, 2, 5, 6, 15, 30)

서로소인 경우 (두 자연수의 최대공약수가 1인 경우)
1, 30 (합 31)
2, 15 (합 17)
5, 6 (합 11)

뒤로 갈수록 갭이 작아져 합이 제일 작음 (5, 6)

 

해당 쌍은 서로소일 뿐이지 원래 A와 B의 값은 아니므로, 원래 A, B의 값을 구하기 위해 해당 서로소 * 최대공약수를 하여 원래 A, B를 출력해준다.