백준] 2436 - 공약수(한국정보올림피아드 2011, KOI 2011 전국본선)

시간 제한 : 1초

메모리 제한 : 128MB

입력

첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,000,000 이하이다.

출력

첫째 줄에는 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 크기가 작은 수부터 하나의 공백을 사이에 두고 출력한다. 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수 쌍이 여러 개 있는 경우에는 두 자연수의 합이 최소가 되는 두 수를 출력한다.

소스코드

#include <iostream>
#include <math.h>
using namespace std;
int gcd(int a, int b)
{
	if (a < b)
		return gcd(b, a);
	if (b == 0)
		return a;
	else
		return gcd(b, a%b);
}
int main(void)
{
	long long g, l, div, ans, min;;
	cin >> g >> l;
	div = l / g;
	min = div, ans = 1;
	for (int i = 1; i <= sqrt(div); i++)
	{
		if (div%i == 0)
		{
			if (gcd(i, div / i) != 1)
				continue;
			if (abs(i - div / i) < min)
			{
				min = abs(i - div / i);
				ans = i;
			}
		}
	}

	cout << ans * g << ' ' << l / ans;
}

Tip

최대공약수(gcd)와, 최소공배수(lcm)을 통해서 두 수를 구할 수 있다. 그 부분만 이해할 수 있으면 문제되지 않는데, 이상한 곳에서 계속 틀렸었다...