[Baekjoon] [2436 : 공약수]

이번 문제는

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

2436번: 공약수

 

 

최대공약수와 최소공배수를 이용해서 역으로 숫자를 찾는 문제입니다. 

 

처음에는 어떻게 하지..?? 하다가 수학적 지식이 있으면 쉽게 방법을 찾을 수 있었습니다.

 

풀이 방법

---

처음에는 최대공약수 g와 최소공배수 l을 보고

l에서 뭔가 약수들을 g로 넘겨주면서 곱하다보면 g*l = a*b가 되는 점을 이용하여 구할 수 있을거 같았는데,

우선 거기서 오버플로우가 일어나기 쉽고 이런 식으로 구하면 결과값으론 최대공약수, 최소공배수가 안 맞는 값들이 나옵니다.

 

 

예를들면 6 20 에서 12 10이 나올수가 있죠.

 

그래서 좀 더 생각해봤는데

 

최대공약수의 성질로 결과인 a, b는 모두 g라는 공약수를 갖습니다. l도 g라는 약수를 가지죠.

 

이제부터 A = g*a, B = g*b라고 합시다 (우변의 a, b는 서로소)

그리고 g*l = A*B임을 생각하면

 

g*l = g*a*g*b이고

 

양변을 g^2으로 나누면 l/g = a*b (a,b는 서로소)가 됩니다.

 

우리는 그러면 l/g가 되는 순서쌍을 찾으면 되고(for 문으로), 앞서 그 순서쌍의 합이 최소이고 두 수가 서로소인것을 찾으면 됩니다.

 

그걸 염두하여 코드를 작성합시다.

 

#include<stdio.h>
#include<limits.h>

long long int gcd(long long int a, long long int b)
{
    return b? gcd(b, a%b) : a;
}

int main(void)
{
    long long int g, l;
    long long int i;
    long long int min = INT_MAX;
    long long int a, b;
    int tmp;
    
    scanf("%lld %lld",&g, &l);
    
    for(i=1; i*i<=(l/g); i++)
    {
        if((l/g)%i == 0)
        {
            tmp = (l/g)/i;
            if(gcd(tmp,i) == 1)
            {
                if(min > tmp+i)
                {
                    min = tmp+i;
                    a = i*g;
                    b = tmp*g;
                }
            }
        }
    }

    printf("%lld %lld",a, b);
    
    return 0;

}

 

 

서로소의 판별을 위하여 gcd라는 최대공약수를 구하는 함수를 만들었습니다.

 

최대공약수가 1이면 서로소니까요 :)

혹시 몰라서(아니 자꾸 틀렸대잖아요) long long int로 모두 사용했습니다.

 

 

if((l/g)%i == 0) 이 부분은 약수인지 판별하는 부분 (순서쌍)

if(gcd(tmp, i) == 1)은 순서쌍의 두 수가 서로소인지 판별

나머지 if는 두 수의 합이 최소인지 판별하는 부분입니다.