[C++] 백준 BOJ 2436번 공약수

두 수가 주어지고 그 수가 어떤 두 수의 최대공약수와 최소공배수이다. 

찾아야하는 두 수를 A, B라고 하고, 최대공약수를 G, 최소공배수를 L라고 두자.

그렇다면

$$A=aG, B=bG $$ (단, a와 b는 서로소 ∵G가 최대공약수) 라고 표현할 수 있고, 

$$L=abG$$라고 볼 수 있다. 

 

문제에서 주어진 것은 G와 L이므로 L/G=a×b라는 것을 얻어낼 수 있다. 

그런데 여기서 a와 b는 서로소이므로 L/G의 약수의 짝 중 서로소인 것을 찾아야만 한다.

문제에서 A와 B의 합을 최소로 하라고 하였지만 A=a×G, B=b×G이므로, 단순히 a+b의 최솟값만 찾아도 된다.

여기서 C=L/G=a×b라고 두면

 

$$b=\frac{C}{a},      y=a+b=a+\frac{C}{a}$$

$$\frac{dy}{da}=1-\frac{C}{a^{2}}$$

$$a=\sqrt{C} 일때 최소값$$

라는 것을 알 수 있다. (서로소 조건으로 만족되지 않는다면 a=C^(1/2)에 가장 가까운 a를 골라주어야한다.)

 

서로소 조건을 확인하기 위해 유클리드호제법을 사용하여 두 수의 최대공약수가 1인지 확인하였다. 

#include <iostream>
using namespace std;
int G, L, C, di;
//유클리드 호제법을 사용하여 최대공약수 구하기
int GCD(int a, int b){
  int temp;
  while(b){   
    temp=a%b;
    a=b;
    b=temp;
  }
  return a;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>G>>L;
    
    C=L/G;
    for(int i=1;i*i<=C;i++){
        if(C%i==0){
            if(GCD(i, key/i)==1)//약수의 짝이 서로소인지 확인
                di=i;
        }
    }
    cout<<di*G<<' '<<(C/di)*G;
    return 0;
}

C=L/G라고 둘 때 시간복잡도

$$\sqrt{C}log(a+b)$$

 (∵유클리드 호제법의 시간복잡도가 log(a+b) 

로 해결