Day 178-Q1 — 2026-10-14 | 引く倍数に上限 K のあるユークリッドゲームの和（鎖の値は周期 K+1 で回る。商を K+1 で割った余りで畳み、勝ち手の数まで数える）

問題

正の整数の組が $N$ 個あり、$i$ 個目は $(a_i,b_i)$ である。整数 $K$ が与えられる。2 人が交互に次の手を指す。

• 両方とも正の組を 1 つ選び、大きい方から小さい方の $k$ 倍（$1\le k\le K$）を引く（結果は 0 以上）。2 つが等しいときはどちらから引いてもよい（結果は同じ）
• 片方が 0 になった組では、もう手が指せない

手が指せないプレイヤーの負けである。両者が最善を尽くすとき、先手が勝つなら First、後手が勝つなら Second を 1 行目に出力せよ。2 行目には、先手の勝ちにつながる最初の手の数を出力せよ（手は「どの組を、どの組に変えるか」で区別する。後手勝ちなら 0）。

入力形式

N K
a_1 b_1
...
a_N b_N

制約

入出力例

2 1
5 2
4 4

First
2

（$K=1$ は「1 回ずつ引く」ゲーム。$g(5,2)=0$、$g(4,4)=1$ で XOR は 1。制限なし（Day177-Q3）では同じ入力が後手勝ちだった）

3 2
10 3
7 5
100 1

First
3

（$g(10,3)=0$、$g(7,5)=0$、$g(100,1)=1$。勝ち手は 3 組すべてに 1 つずつある。$(10,3)$ は $g=0$ なのに、3 の 2 倍を引いて値 1 の局面 $(4,3)$ へ動ける（1 倍を引いた $(7,3)$ は値 2）。Nim の流儀で「$t<g_i$ の組」だけを数えると 1 になって誤る）

2 1000000000000000000
5 2
4 4

Second
0

（$K$ がすべての商より大きければ制限なしと同じ。Day177-Q3 の入力例 2 と同じ答え。3 例とも全状態の Grundy 数による全探索と一致）

背景と出典

概念図

ヒント（クリックで段階的に開示）

模範解答 (Python)

📋 コピーimport sys


def main():
    data = sys.stdin.buffer.read().split()
    n, K = int(data[0]), int(data[1])
    P = K + 1                     # 鎖の値の周期
    gs = []
    info = []
    for i in range(n):
        a = int(data[2 + 2 * i])
        b = int(data[3 + 2 * i])
        if a < b:
            a, b = b, a
        qs = []
        while b:
            qs.append(a // b)
            a, b = b, a % b
        x = 0                     # (d, 0) は終局で値 0
        for q in reversed(qs[1:]):
            j = q % P             # h_q = h_{q mod (K+1)}
            x = x if j == 0 else (j - 1 if j <= x else j)
        q = qs[0]
        j = q % P
        g = x if j == 0 else (j - 1 if j <= x else j)
        gs.append(g)
        info.append((q, x))
    G = 0
    for g in gs:
        G ^= g
    if G == 0:
        print("Second")
        print(0)
        return
    cnt = 0
    for g, (q, x) in zip(gs, info):
        t = G ^ g
        if q > K:                 # 窓は連続 K 個 → {0..K} から g を除いた全部
            cnt += t <= K
        elif t == x:              # q <= K: 制限なしと同じ鎖 h_0..h_{q-1}
            cnt += 1
        elif t < x:
            cnt += t <= q - 2
        else:
            cnt += t <= q - 1
    print("First")
    print(cnt)


main()

計算量: 1 組あたり互除法の段数 $O(\log\max(a,b))$。$N=2\times10^5$ で乱数（$K$ も乱数）0.70 s、$K=3$ でも 0.70 s、全組が隣り合うフィボナッチ数（商がすべて 1 の最悪ケース）で 1.55 s、いずれも約 70 MB（Python 3.14.8、Apple M5 Pro、負荷平均 15〜20 での実測、起動込み）。

Step-by-Step 解説

迷った他案と採らなかった理由

前提が変わったら

• 引く倍数の下限もある（$L\le k\le K$）なら、窓が $[j-K,\ j-L]$ になり、連続する値が互いに異なるとは限らない。周期は $L+K$ 程度になりそうだが、本セッションでは調べていない
• 組ごとに $K_i$ が違うなら、式の $K$ を組ごとに替えるだけで同じく解ける（周期性の議論は組の中で閉じている）
• misère（最後に指した人の負け）なら XOR が使えない。Day177-Q3 と同じく未調査

よくあるミス

次のステップ

• 発展1: 下限つき（$L\le k\le K$）の版で鎖の値の列を全探索で調べ、周期と前周期を求める
• 発展2: 「勝ち手を 1 つ出力」に変え、$q>K$ の組で値 $t$ を持つ $j$ を $O(1)$ で逆算する（$j\equiv$ 値の位置 $\pmod{K+1}$ を窓の中から選ぶ）
• 発展3: Day177-Q3 と合わせ、組ごとに $K_i$ が違う和を作って検算する

自己評価

自分の回答

気づき・メモ