問題
正の整数の組が $N$ 個ある。$i$ 個目は $(a_i,b_i)$ である。2 人が交互に次の手を指す。
- 両方とも正の組を 1 つ選び、大きい方から小さい方の正の倍数を引く（結果は 0 以上）。2 つが等しいときはどちらから引いてもよい（結果は同じ）
- 片方が 0 になった組では、もう手が指せない
手が指せないプレイヤーの負けである。両者が最善を尽くすとき、先手が勝つなら First、後手が勝つなら Second を 1 行目に出力せよ。2 行目には、先手の勝ちにつながる最初の手の数を出力せよ（手は「どの組を、どの組に変えるか」で区別する。後手勝ちなら 0）。
入力形式
N
a_1 b_1
...
a_N b_N制約
| # | 制約 |
|---|---|
| 1 | $1\le N\le2\times10^5$ |
| 2 | $1\le a_i,b_i\le10^{18}$ |
入出力例
入力例1
1
3 2出力例1
Second
0（$(3,2)\to(1,2)\to(1,1)\to(1,0)$ と一本道。比 $3/2<\varphi$ なので 1 組だけなら後手勝ち）
入力例2
2
5 2
4 4出力例2
Second
0（1 組ずつ見ると $(5,2)$ も $(4,4)$ も先手勝ちだが、和は後手勝ち。$g(5,2)=1$、$g(4,4)=1$ で XOR が 0。商 $q$ をそのまま Grundy 数とみなすと $2\oplus1=3$ で誤る）
入力例3
3
10 3
7 5
100 1出力例3
First
1（$g(10,3)=2$、$g(7,5)=0$、$g(100,1)=100$ で XOR は 102。勝ち手は $(100,1)\to(2,1)$ の 1 つだけ。3 例とも、全状態の Grundy 数による全探索と一致）
背景と出典
- ユークリッドゲームは Cole–Davie “A game based on the Euclidean algorithm and a winning strategy for it”（Mathematical Gazette, 1969 と記憶）で、1 組なら「$a=b$ か、大きい方 / 小さい方 $>\varphi$ なら先手勝ち」と示された、と私は記憶している（原典は本セッションで未確認）。本セッションでは $a,b<200$ の全組で、この規則と「Grundy 数 $\ne0$」が一致することを確かめた
- Grundy 数については Nivasch “The Sprague–Grundy function of the game Euclid”（Discrete Mathematics, 2006 と記憶、未確認）が閉じた式を与えたと記憶している。本問の解は論文の式ではなく、鎖の構造から自分で導いた漸化式で、$a,b<400$ の全 159201 組で全探索と一致した
- 本問の問題文・制約・入力例は自作
概念図
ヒント（クリックで段階的に開示）
ヒント1（方向性）
$a\ge b$、$a=qb+r$（$0\le r<b$）とする。$(a,b)$ から行けるのは $(r+kb,\ b)$（$k=0,\dots,q-1$。$k=0$ は $(r,b)$ で、大小が入れ替わる）だけ。しかも $(r+kb,b)$ から行けるのは $(r+jb,b)$（$j<k$）だけ。つまり「鎖」になっている。
ヒント2（アプローチ）
鎖の値を $h_k=g(r+kb,b)$ とすると、$h_0=g(b,r)=:x$ で、$h_k=\operatorname{mex}\{h_0,\dots,h_{k-1}\}$。
- $x=0$ なら $h_k=k$
- $x\ge1$ なら $h_1=0,h_2=1,\dots,h_x=x-1$、そこで $x$ が既に使われているので $h_{x+1}=x+1$、以後 $h_k=k$
求めたいのは $g(a,b)=h_q$。
ヒント3（誘導）
- $g(qb+r,b)=q-1$（$q\le x$ のとき）、$q$（$q>x$ のとき）。$r=0$ なら $x=g(b,0)=0$
- 互除法の商の列 $q_1,q_2,\dots,q_m$ を集め、$x=0$ から後ろへ $x\leftarrow q_j-[q_j\le x]$ と畳む
- 勝ち手: 全体の XOR を $G$ とし、組 $i$ の行き先の値の集合 $\{h_0,\dots,h_{q-1}\}$ に $G\oplus g_i$ が入っていれば 1 手。値はすべて異なるので、入っていればちょうど 1 手
模範解答 (Python)
模範解答を表示する（まず自力で解いてから）
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
gs = [] # 各ゲームの Grundy 数
reach = [] # 各ゲームから 1 手で行ける Grundy 数の集合を (q, x) で表す
for i in range(n):
a = int(data[1 + 2 * i])
b = int(data[2 + 2 * i])
if a < b:
a, b = b, a
qs = []
while b: # ユークリッドの互除法で商の列を集める
qs.append(a // b)
a, b = b, a % b
x = 0 # 最後の (b, 0) は手が無いので 0
for q in reversed(qs[1:]): # 下から g = q - [q <= x] を畳み込む
x = q - 1 if q <= x else q
q = qs[0]
gs.append(q - 1 if q <= x else q)
reach.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, reach):
t = G ^ g
# 行ける値: h_0 = x、h_k (1<=k<=q-1) は k<=x なら k-1、k>x なら k
if t == x:
cnt += 1
elif t < x:
cnt += t <= q - 2 # k = t+1 <= min(q-1, x)
else:
cnt += t <= q - 1 # k = t (x < k <= q-1)
print("First")
print(cnt)
main()計算量: 1 組あたり互除法の段数 $O(\log\max(a,b))$（$10^{18}$ 以下で最大 86 段程度、隣り合うフィボナッチ数が最悪）。$N=2\times10^5$ で乱数 0.55 s、全組が隣り合うフィボナッチ数の最悪ケースで 1.15 s（Python 3.14.8、Apple M5 Pro、負荷平均 4〜13 での実測、起動込み）。
Step-by-Step 解説
11 手で行ける局面は鎖
$(qb+r,b)$ から $b$ を $k$ 回引くと $((q-k)b+r,\ b)$。$k=q$ まで引けて、最後は $(r,b)$（$r=0$ なら終局）。行き先は $(r+jb,b)$ の $j=0..q-1$ で、そのどれもが自分より小さい $j$ にしか行けない。$j=0$ の $(r,b)$ だけは大小が入れ替わって、別の組 $(b,r)$ の世界に入る。
2鎖の Grundy 数
$h_0=x=g(b,r)$。$h_k$ は $h_0..h_{k-1}$ の mex。$x$ が 1 つだけ「先取り」されているので、$0,1,2,\dots$ の列から $x$ を 1 つ飛ばした列になる。
$$h_k=\begin{cases}k-1&(1\le k\le x)\\ k&(k>x)\end{cases}$$
$g(a,b)$ は鎖の次の項 $h_q$ と同じ（行き先が $h_0..h_{q-1}$ だから）。
3畳み込み
$(a,b)\to(b,r)\to\cdots$ と互除法を下り、最後の $(d,0)$ の値 0 から逆にたどる。各段で $x\leftarrow q-[q\le x]$。$q\ge1$ なので値は 0 にもなりうる（$q=1$ かつ $x\ge1$）。これがちょうど「比が $\varphi$ 未満で、次の局面が先手勝ち」という古典的な負け局面の条件と一致する。
4和と勝ち手の数
Sprague–Grundy の定理で、和の値は各組の XOR。勝ち手は組 $i$ を値 $t=G\oplus g_i$ の局面に変える手。行ける値は $\{x\}\cup\{0,\dots,\min(q-1,x)-1\}\cup\{x+1,\dots,q-1\}$ で互いに異なる。場合分けすると、$t<g_i$ の値には Nim と同じく必ず行ける。違いは $q\le x$ のとき、$g_i=q-1$ より大きい $t=x$ にも行けること（鎖の先頭 $h_0$）。Nim の流儀で $t<g_i$ だけを数えると、先手勝ちの 1585 個中 148 個で勝ち手の数を少なく数えた（実測、取りこぼし計 153 手）。
5値の大きさ
Grundy 数は $q$ 程度、つまり $10^{18}$ まで大きくなる（$(10^{18},1)$ の値は $10^{18}$）。Python の整数ならそのまま XOR できる。
迷った他案と採らなかった理由
| 案 | 計算量 | 採否 | 理由 |
|---|---|---|---|
| Grundy 数の表（メモ化） | $O(A^2\cdot A)$ | 検算用のみ | $a,b\le10^{18}$ では不可能 |
| 1 組ごとの勝敗（$\varphi$ 規則）を 0/1 の Nim の山にする | $O(\log)$ | 不採用（誤り） | 2000 個の和で 584 個の勝敗を誤る（実測）。入力例 2 |
| 商 $q$ をそのまま Grundy 数にする | $O(1)$ | 不採用（誤り） | 2000 個中 409 個の勝敗を誤る（実測）。入力例 2 |
| 勝ち手を「$t<g_i$ の組の数」で数える（Nim の流儀） | $O(1)$ | 不採用（誤り） | $t<g_i$ には必ず行けるが、$q\le x$ のとき $t=x>g_i$ にも行ける。先手勝ち 1585 個中 148 個で数え落とす（実測） |
| Nivasch の閉じた式 | $O(\log)$ | 不採用 | 原典を確認できず、式も覚えていない。鎖からの漸化式なら導出と検算が手元で閉じる |
| 商の列を後ろから畳む（本解） | $O(N\log V)$ | 採用 | 0.55〜1.15 s |
前提が変わったら
- misère（最後に指した人の負け）なら Grundy 数の XOR は使えない。全組の値が 1 以下かどうかで場合分けする Nim の misère 規則が、このゲームにそのまま当てはまるかは調べていない
- 引く倍数に上限（例: 高々 $K$ 倍）があれば鎖が途中で切れ、$h_k$ の列は mex の窓が $K$ 個になる（周期的な列）。漸化式は作り直しになる
- 1 組のゲームで勝ち手を 1 つ出せなら、$t=0$ になる $k$（$x=0$ なら $k=0$、$x\ge1$ なら $k=1$）をそのまま返せばよい
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 勝敗（$\varphi$ 規則）を XOR する | 1 組の解き方で和も解けると思う | 和には Grundy 数が要る（入力例 2） |
| $g=q$ とする | $x$ の飛ばしを忘れる | $g=q-[q\le x]$ |
| 再帰で $g(b,r)$ を呼ぶ | 段数は 90 程度で深くはないが、$2\times10^5$ 組では関数呼び出しが重い | 商の列を集めてループで畳む |
| 勝ち手を「$t<g_i$ の組の数」で数える | Nim の勝ち手の数え方の流用 | 鎖の先頭 $h_0=x$ が $g_i$ より大きいことがある。行ける値の集合 $\{x\}\cup\dots$ で判定する |
| $a=b$ の組を特別扱いし忘れる | $q=1,r=0$ を別の場合と思う | $r=0$ なら $x=0$ で $g=q=1$。式のままで正しい |
次のステップ
- 発展1: 引く倍数が高々 $K$ 倍のユークリッドゲームで、鎖の値の列を求め直す
- 発展2: Nivasch の論文の式を確認し、本問の漸化式と同じ値になることを $a,b<1000$ で照合する
- 発展3: 本問の misère 版を全探索で調べ、Nim の misère 規則が通用するか確かめる
検証ログ（本セッションで実行した数値）
- 1 組の Grundy 数（実測）: $1\le a,b<400$ の全 159201 組で、メモ化 mex の全探索と漸化式が全件一致（値の最大 399）
- $\varphi$ 規則（実測）: $1\le a,b<200$ の全組で「$a=b$ または比 $>\varphi$」と「Grundy 数 $\ne0$」が一致
- 和と勝ち手の数（実測）: 1〜4 組・各値 200 以下の 2000 個、1〜3 組・各値 60 以下の 600 個で、勝敗と勝ち手の数（全手を列挙して XOR が 0 になる手を数えた）が全件一致
- 誤った方法（実測、2000 個）: 商を Grundy 数に 409、勝敗を 0/1 の山に 584 で勝敗を誤る。勝ち手を $t<g_i$ だけで数えると、先手勝ちの 1585 個中 148 個で数が合わない
- 時間（実測、起動込み、$N=2\times10^5$）: 乱数（$10^{18}$ 以下）0.55 s、隣り合うフィボナッチ数 $(679891637638612258,420196140727489673)$ を全組に 1.15 s
- 扱っていない範囲: 原典（Cole–Davie、Nivasch）の確認、misère 版、倍数に上限のある版