백준 2436번 공약수

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

2436번: 공약수

두 정수 $A$, $B$가 주어질 때 $A$가 최대공약수, $B$가 최소공배수인 두 수를 찾는 문제입니다. 

 

풀이

조건에 맞는 두 수를 $N$, $M$이라고 하면

$N, M$의 최대공약수는 $A$, 최소공배수는 $B$이므로

$A\times i = N, A\times j = M$ (단, $i, j$는 서로소)

$N\times k = B, M\times l = B$ (단, $k, l$은 서로소)

 

$N, M$에 위 식을 대입하면 

$A\times i\times k = A\times j\times l=B$

$i\times k = j\times l = B\div A$

 

따라서 $B\div A$의 약수 중 서로소 조건을 만족하는 $i, j, k, l$을 찾으면 됩니다.

 

조건을 만족하는 $N, M$중 합이 가장 작은 경우를 출력해야 하며, 

$N+M = A\times (i + j)$이므로 $i, j$의 합이 가장 작은 경우를 찾아야 합니다.

$i = l, k = j$로 두고 $B\div A$의 약수이면서 서로소인 $i, j$를 찾으면 답을 구할 수 있습니다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
int gcd(long long a, long long b) {
    if (b)
        return gcd(b, a % b);
    return a;
}
int main() {
    long long a, b, d, i = 1;
    cin >> a >> b;
    d = b / a;
    for (long long t = 2; t * t < d; t++) {
        if (d % t == 0) {
            int n = gcd(t, d / t);
            if (n == 1)
                i = t;
        }
    }
    cout << a * i << ' ' << a * (d / i);
    return 0;
}