백준 2436 c++ 풀이

 

전략:

1. 1부터 루트(gcd*lcm)까지 작은 자연수를 설정한다.

2. 만약 그 자연수와 gcd*lcm/자연수의 GCD값이 주어진 gcd값과 같으면 result에 대입하고 출력한다.

코드:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll GCD(ll a, ll b){
	if(b==0){
		return a;
	}
	return GCD(b, a%b);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll gcd, lcm;
	cin>>gcd>>lcm;
	ll result1, result2;
	for(ll i= 1; i*i<=gcd*lcm; ++i){
		ll a = i, b= gcd*lcm;
		if(b%a!=0){
			continue;
		}
		b/=a;
		if(GCD(a, b)==gcd){
			result1 = a;
			result2 = b;
		}
	}
	cout<<result1<<" "<<result2<<"\n";
}