[BOJ] 2436번: 공약수

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

우선 두 자연수의 곱이 동일할 경우, 합이 최소가 되려면 두 수의 차가 최소여야합니다. 그렇기에 주어진 최대공약수/최대공배수를 만족하면서 두 수의 차가 최소인 쌍을 찾아야합니다.

최대공약수를 g, 최대공배수를 l, 두 수를 A와 B라고 할 때 자명하게

A=ga, B=gb, gcd(a,b)=1, ab = l/g가 됩니다. 그렇기에 저희는 곱이 l/g가 되면서 차는 최소인 두 수 a, b를 구하는 것으로 문제를 바꿔 생각할 수 있습니다.

이는 주어진 l/g에 대해 1부터 sqrt(l/g)까지로 나눠보면서 판단할 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/2436.cpp