mayoko’s diary

プロコンとかいろいろ。

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