题解 P4860 【Roy&October之取石子II】

· · 题解

之前做P4016的时候看了题解，初步了解了博弈论的基本做题方法，现在举一反三，用相似的解法完成这道题。

题目要求显然就是可以取1和全体质数，即\{1,2,3,5,7...\}。以此进行归纳分析：

  1. 当N=1,2,3时，显然先手可以一次全部拿完，胜。
  2. 当N=4时，先手只能拿1,2,3个，剩下的被后手拿走，负。
  3. 当N=5,6,7时，先手先拿1,2,3个，这时还剩4个，转化为情况2，胜。
  4. 当N=8时，若先手拿1个，则后手直接拿7个；若先手拿质数个，由哥德巴赫猜想，剩下的也是质数个，后手直接全部拿完即可，负。

综上所述：

  1. 若N=1,2,3，则显然先手必胜。
  2. 若N=4k(k∈Z_+),则N为偶数，由哥德巴赫猜想，若先手拿质数个，质数当然不是4的倍数，变为情况3，后手胜；若先手拿一个，后手拿三个，此时N仍为4的倍数，循环下去后手也能拿到最后一个，后手必胜。
  3. 若N=4k+1,4k+2,4k+3(k∈Z_+),则先手先拿1,2,3个，此时N变为4k，转化为情况2，先手必胜。

代码就不注释了：

#include <bits/stdc++.h>
using namespace std;

int T,N;

int main()
{
    scanf("%d",&T); while (T--)
    {
        scanf("%d",&N);
        puts((N%4)?"October wins!":"Roy wins!");
    }
    return 0;
}