Codeforces #426(Div. 2) C - The Meaningless Game - ふーらくたるの雑の記

問題

SlastyonaとPushokがヒントなしの数当てゲームをしている。数当てゲームは0回以上のラウンドからなっており、各プレイヤーは最初、得点として1が与えられている。各ラウンドごとに当てなければならない数 $k$ が与えられ、そのラウンドの勝者の得点は $k^2$ 倍、敗者の得点は $k$ 倍されることになる。 $n$ 個の得点の組 $(a, b)$ が与えられるので、その組が各ゲームの最終結果としてありうるかどうかを判定せよ。

解説

SlastyonaとPushokという名前は長すぎるので以降、それぞれプレイヤーS、Pと呼ぶことにします。後自然数は0を含みます。

まず、当てなければならない数 $k$ は全て素数であると仮定できます。これは例えば $20=2^2\cdot 5$ を当てた時の得点倍率が2を2回、5を1回当てた時の得点倍率と等しいことからわかります。

次に一つの素数 $p$ しか使われていないゲームを考えます。Sが勝った回数を $x$ 、Pが勝った回数を $y$ 、Sの最終得点を $a$ 、Pの最終得点を $b$ とすると、このとき $a=p^{2x+y}$ 、 $b=p^{x+2y}$ と表すことができます。これより与えられた入力 $(a, b)$ がゲームの結果としてありうるということは、ある自然数 $x, y$ が存在して、 $a=p^{2x+y}$ 、 $b=p^{x+2y}$ を満たすことに言い換えられるようになりました。

ここで、ある自然数 $x$ 、 $y$ が存在して、 $a=p^{2x+y}$ かつ $b=p^{x+2y}$ を満たすことというのは、 $c^3 = a \cdot b$ かつ $a\bmod c=0$ かつ $b\bmod c=0$ を満たす自然数 $c$ が存在することと同値です。この命題について証明します。

⇒方向については、 $a \cdot b = p^{3(x+y)}$ と $2x + y \geq x + y \land x + 2y \geq x + y$ より、自然数 $p^{x+y}$ が条件を満たすことが明らかです。

逆を示します。 $a = p^{X}, b = p^{Y}, c = p^{d}$ とおきます(ただし $X$ 、 $Y$ 、 $d$ は自然数)。 $c^3 = a \cdot b$ より、 $X + Y = 3 d$ が成り立ち、さらに $a\bmod c=0$ かつ $b\bmod c=0$ より $X \geq d$ かつ $Y \geq d$ が成り立ちます。このとき、 $2 x + y = X$ かつ $x + 2y = Y$ を満たすような自然数 $x, y$ が存在することを示します。
$2 x + y = X$ 、 $x + 2y = Y$ より $3x + 3y = X + Y$ 。 $X + Y = 3 d$ であるから $3x + 3y = 3d$ 。ゆえに $x + y = d$ 。
$2x + y = X$ と $x + y = d$ より $x = X - d$ 。 $X, d$ が自然数であることと、 $X \geq d$ より $x$ は自然数。同様にして上の連立方程式の解である自然数 $y$ が存在することも示せます。よって逆も示すことができました。

以上より、ある自然数 $x$ 、 $y$ が存在して、 $a=p^{2x+y}$ かつ $b=p^{x+2y}$ を満たすこと、すなわち最終結果が $(a, b)$ となるようなゲームの進行方法が存在するということは、 $c^3 = a \cdot b$ かつ $a\bmod c=0$ かつ $b\bmod c=0$ を満たす自然数 $c$ が存在することと同値であるということが示せました。

上の考察は一つの素数のみ使われていたゲームについてのものでした。しかし異なる素数は独立に考えることができるということに気づくと、ゲームで使われた任意の素数それぞれについて上の条件が成り立っているかどうかを調べればよいことがわかります。よって複数の素数が使われているゲームに対しても $a \cdot b$ の立方根 $c$ に対して、 $a\bmod c=0$ かつ $b\bmod c=0$ が成り立つかどうかを調べればいいことがわかりました。立方根は二分探索で求めることができるので、以上より $O(n\log(ab))$ の解法を得ることができました。

ソースコード

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        ll a, b;
        scanf("%lld %lld", &a, &b);

        ll ok = 0, ng = 1500000LL;
        while (ng - ok > 1) {
            ll mid = (ng + ok) / 2;
            if (mid * mid * mid <= a * b) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        ll c = ok;

        if (c * c * c == a * b && a % c == 0 && b % c == 0) {
            puts("Yes");
        } else {
            puts("No");
        }
    }
    return 0;
}

感想

コンテスト中はこんなだらだら証明を書かないで、適当に変形して「どうせ必要十分だろ!w」と思って投げたら通りました。