SRM535 Div1 Easy - FoxAndGCDLCM
解法
gcd=gということはaもbもgの倍数であることは確定する
a=gx, b=gy (xとyは互いに素)とおくと
gl = ab = gxgy ∴ xy = l/g
となるから、xとyはl/gの約数を全通り試せば十分
l/gはたかだか10^12だから約数全列挙ができる
(lがgで割り切れない場合はもちろん解なし)
class FoxAndGCDLCM { public: ll get(ll g, ll l) { if (l%g) return -1; ll res = 1ll<<60, t = l/g; for (ll i=1; i*i<=t; i++) if (t%i==0) { ll a = g*i, b = g*(t/i); if (gcd(a,b)==g) chmin(res, a+b); } return res; } };