SRM535 Div1 Easy - FoxAndGCDLCM

問題

gcdがgでlcmがlとなるような2つの自然数(a,b)の組み合わせのうちa+bの最小値を求めよ
ただしそういう組み合わせが存在しない場合は-1を返す

1 <= g, l <= 10^12

解法

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;
	}
};