自动搬运

查看原文

来自洛谷，原作者为

	Ofnoname 亡者归来

搬运于2025-08-24 22:04:39，当前版本为作者最后更新于2019-02-15 21:23:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

之前做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;
}