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

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

 

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

2436번: 공약수

 

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

$$a=g{a}^{\prime },b=g{b}^{\prime },lcm=g{a}^{\prime }{b}^{\prime }$$

 

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

 

제가 작성한 소스입니다.

//------------------------------------------------
//    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; }
    }
}