백준 문제 2436번 공약수 문제풀이 c++

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

2436번: 공약수

 

문제해석

 

최대 공약수를 x 최소 공배수를 y라고 하면

 

x*y값의 약수 쌍 중 최소가 되면서 그 둘의 최대 공약수가 x가 되는 값을 찾으면된다.

 

나는 최소 공배수를 최대 공약수로 나눠서 그 값을 z=y/x로 두었고 z의 약수 쌍중 최소가되면서 최대 공약수가 1인것인 쌍을 찾은수 그 둘에 각각 x를 곱해서 출력하였다.

 

최대 공약수를 구하는 것은 유클리드 호재법을 사용하여 구하였다.

 

코드

 

#include <iostream>
typedef long long int ll;
#include <algorithm>
using namespace std;
ll gcd(ll n,ll m);
int main(){
	cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    ll sum=9223372036854775807;
    ll ans1,ans2;
    ll x,y,z;
    cin>>x>>y;
    z=y/x;
    for(ll i=1; i*i<=z; i++)
    {
        if((z%i)==0)
        {
            if(i+(z/i)<=sum&&gcd(i,z/i)==1)
            {
                sum=i+z/i;
                ans1=i;
                ans2=z/i;
            }
        }
    }
    cout<<x*ans1<<" "<<x*ans2;
}
ll gcd(ll n,ll m){
    if(n>m)
    {
        ll tmp=n;
        n=m;
        m=tmp;
    }
    if(n==0)
    {
        return m;
    }
    else
    {
        return gcd(m%n,n);
    }
}