boj 2436 - 공약수

http://boj.kr/2436

Baekjoon Online Judge

문제 설명

최대 공약수와 최소 공배수 a,b가 주어질때 이를 만족하는 수

n,m의 합이 최대가 되도록 하는 문제입니다.

 

풀이 과정 1

n = a*n'

m = a*m'

a는 최대 공약수를 의미합니다.

최소 공배수는 

두 수의 곱 나누기 최대 공약수 즉

b = n*m/a

n,m을 치환 한다면

b = (a * n') * (a * m') / a

이므로 b = a * n' * m'입니다.

 

풀이 과정 2

일단 a,b의 범위가 1억까지 주어진 것을 보면

O(n)이하의 시간복잡도가 요구 됩니다.

근데 무작위로 두 수를 다 곱해보면 시간이 초과가 됩니다.

그래서 머리를 쓰자면 n',m'을 구하고,거기에 최대 공약수를 

곱해보는건 어떨까? 입니다.

b / a = n' * m'입니다.

즉 우리는 곱하였을 때 b/a가 되는 두 수를 

찾아야하고,n',m'은 서로소여야합니다.

연산을 더 줄이기 위해 조건 하나를 더 걸어보겠습니다.

n'<=m' 이 조건입니다.

이렇게 된다면 b/a의 인수인 n'는 m'이하이니,

1~루트(b/a)까지 n'을 해보며 m'가 정수인지,

정수라면 서로소인지를 체크하고,그 더한 값이

구한 값보다 크다면 갱신해주면 됩니다.

 

 

정답 소스(위 코드는 비효율적일수 있습니다.)

#include<bits/stdc++.h>
using namespace std;
int gc,lc,ans=1e9;
int G(int a,int b){
    if(b==0)return a;
    return G(b,a%b);
}
int main(){
    int a=0,b=0;
    scanf("%d %d",&gc,&lc);
    int k=lc/gc;


    for(int i=sqrt(k);i>=1;i--){
        if(k%i==0){
            if(G(k/i,i)==1){
                a=i;
                b=k/i;
                break;
            }

        }
    }
    printf("%d %d",a*gc,b*gc);
}

참고 자료

https://only-cpp.tistory.com/4

https://only-cpp.tistory.com/3