洛谷 P4018 Roy&October之取石子

题意：\(n\) 个石头，每次取 \(p^k\) 个石子（\(p\) 是质数，\(k\in \N\)），取完最后一个的人获胜，问谁有必胜策略。

只能说，MO 题真的猛！

结论：\(n\bmod 6=0\) 时，先手必败，否则必胜。

证明：

考虑数学归纳法。

首先 \(n\in [1,5]\) 时，先手必胜，一步取完。

\(n=6\) 时，因为 \(6\) 一定是 \([1,5]\) 中两个数之和，先手必败。

当 \(n=6k(k>1)\) 时，因为 \(6=2\times 3\)，先手不可能取 \(6\) 的倍数个石子，所以转化成 \(n=6k+r\)。

当 \(n=6k+r(k>1,r<6)\) 时，先手必定可以取 \(r\)，转化成 \(n=6k\)。

改编题 \(k\in \{0,1\}\)。

结论：\(n\bmod 4=0\) 时，先手必败，否则必胜。

证明：

数学归纳法+哥德巴赫猜想。