コーディング コンテストでパズルを解いていましたが、1 つの質問に行き詰まっています。基本的に、誰かがこの解決策に到達する方法がわかりません。パズルは
アリスとボブは次のゲームをします。彼らは遊ぶ数 N を選びます。ルールは次のとおりです。
- Bob が最初にプレイし、2 人のプレイヤーが交互にプレイします。
- 自分の番に、プレイヤーは N から N 未満の任意の素数 (1 を含む) を引くことができます。このようにして得られた数が新しい N です。
- 手番中に動けなくなった人はゲームに負けます。
両方が最適にプレーすると仮定すると、どちらがゲームに勝つでしょうか?
そして与えられた解は
int main() {
long int T, N;
for(scanf("%ld", &T); T > 0; T--) {
scanf("%ld", &N);
if (N % 4 == 1) {
printf("ALICE wins\n");
} else {
printf("BOB wins\n");
}
}