SRM 635 div1 easy : FoxAndGCDLCM
解法
各素因数に対して (L の指数) >= (G の指数) を満たしていなかったら, すなわち L%G != 0 なら -1 を返します。
そうでない時は, A, B は a = G*a, b = G*b と表されています(a, b は互いに素)。
で, この a, b は 素因数として見ると, 各素因数の指数部の a, b による max 値が L/G の指数部と一致しているはずです。ただ, これはこんな難しく考えなくても, a*b = L/G を満たせば OK です(a と b が互いに素なので)。
ということで, L/G の約数をすべて列挙して互いに素か, を調べていけば良いです。
class FoxAndGCDLCM { public: long long get(long long G, long long L) { if (L%G) return -1; ll mult = L/G; ll ans = 1ll<<55; for (ll i = 1; i*i <= mult; i++) { if (mult%i == 0) { ll j = mult/i; if (__gcd(i, j) > 1) continue; ans = min(ans, i+j); } } ans *= G; return ans; } };