ゲームの選択和に関する問題です。

\(N\) 個の不偏ゲーム \(G_1,G_2,\ldots,G_N\) の選択和 とは、各手番で \(N\) 個のゲームのうち \(1\) つ以上に着手するゲームと定義されます。

本問題であれば、\(G_i\) は最初 \(A_i\) 個の石があり、各手番では石を\(1\) 個以上 \(B_i\) 個以下取り除くゲームと定義した時の \(N\) 個の選択和として得られるゲームの勝敗判定ができれば良いです。

そして、選択和の勝敗判定は以下のように行うことができます：

• \(N\) 個のゲームが全て後手必勝であれば後手必勝、そうでなければ先手必勝である。

証明：

\(N\) 個のゲームが全て後手必勝である状態を \(P\) 状態、そうでない状態を \(N\) 状態と呼びます。

\(P\) 状態であることが後手必勝であることと同値であることを示すためには、以下の \(3\) つを示せば良いです：

• 終了盤面（操作できないような盤面）が \(P\) 状態であること。
• \(P\) 状態からどのように操作しても \(P\) 状態に到達できないこと。
• \(N\) 状態から \(P\) 状態に到達できる操作が必ず存在すること。

この \(3\) つを順に示していきます。

[1] 終了盤面（操作できないような盤面）が \(P\) 状態であること

各ゲームの終了盤面は全て後手必勝なので、\(P\) 状態です。

[2] \(P\) 状態からどのように操作しても \(P\) 状態に到達できないこと

全てのゲームが後手必勝盤面である状態から \(1\) つ以上のゲームに着手する必要があるので、少なくとも \(1\) つのゲームでは先手必勝盤面になります。

[3] \(N\) 状態から \(P\) 状態に到達できる操作が必ず存在すること

先手必勝盤面全てに対して手番を行うことで、全てを後手必勝盤面にすることができます。

以上より、 \(N\) 個のゲームが全て後手必勝であることが後手必勝であることと同値であることが分かりました。

本問題における \(i\) 番目のゲーム \(G_i\) は \(A_i \bmod (B_i+1)=0\) であることが後手必勝であることと同値なので、全ての \(1\le i\le N\) に対し \(A_i \bmod (B_i+1)=0\) が成り立つならば後手必勝、そうでないならば先手必勝、と判定できます。

選択和を使って解ける問題： ARC225-B