SRM535 Div1 250

問題

最小公倍数Gと最大公約数Lが与えられるので、そのようになる2つの整数A,Bのうちでその和が最小になるそのA+Bを返せ。

考え方

L/Gが割り切れないならば、そもそもおかしいので-1。
M=L/G、A'=A/G、B'=B/Gとして、素因数分解したものをA'とB'に割り振れば良い。ように見えたけど、この組み合わせはかなりあるので、無理。
そこで、A'を1から1つずつ見ていく。B'=M/A'になるが、gcd(A',B')==1(互いに素)となることを確認しないとgcd(A,B)==Gにならない。AとBは区別しなくていいので、sqrt(M)まで調べればよいので間に合う。