[C/C++] 백준 #2436 공약수(수학)

보통 두 수가 주어지면, 최대공약수와 최소공배수를 구하는 것을 하지만, 이 문제는 최대공약수와 최소공배수가 주어지면, 그러한 최대공약수와 최소공배수를 가지는 두 수를 구하는 문제입니다.

 

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

2436번: 공약수

 

두 수 \(a, ~ b\)가 주어지면, 두 수의 최대 공약수가 \(g\)일 때, 우리는 다음과 같은 식을 얻을 수 있습니다.

\[ a = ga',  ~ b = gb', ~ lcm = ga' b' \]

 

최소공배수를 최대공약수로 나누면 우리는 \(a' b'\)을 얻을 수 있습니다.  \( (a', ~b') = 1 \)을 만족해야 하는데, 만족하는 쌍이 여러개 나온 경우 그 합이 최소가 되는 것을 골라야 합니다.  \( x + y \ge 2 \sqrt{xy} \) 형태이기 때문에 합이 최소가 되기 위해서는 \( a', ~ b' \) 쌍이 가장 가까워야 합니다.  그렇게 하기 위해서는 제곱근을 구해서 조금씩 멀어지면서 두 수가 서로 소인 경우에 답이 되도록 구현했습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2436 - Common Divisors
//        - by Aubrey Choi
//        - created at 2019-07-23
//------------------------------------------------
#include <stdio.h>
#include <math.h>

int gcd(int a, int b) { while(b) { int t=b; b=a%b; a=t; } return a; }
int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    b /= a;
    for(int r = (int)sqrt(b); r >= 1; r--)
    {
        if(b%r) continue;
        if(gcd(b/r, r)==1) { printf("%d %d\n", a*r, b/r*a); break; }
    }
}