洛谷 P4018：RoyOctober之取石子 ← 巴什博奕（Bash Game）
【题目来源】
https://www.luogu.com.cn/problem/P4018
【题目描述】
Roy 和 October 两人在玩一个取石子的游戏。
游戏规则是这样的：共有 n 个石子，两人每次都只能取 p^k 个（ p 为质数，k 为自然数，且 p^k 小于等于当前剩余石子数），谁取走最后一个石子，谁就赢了。
现在 October 先取，问她有没有必胜策略。
若她有必胜策略，输出一行 October wins!；否则输出一行 Roy wins!。
【输入格式】
第一行一个正整数 T，表示测试点组数。
第 2 行~第 T+1 行，一行一个正整数 n，表示石子个数。
【输出格式】
T 行，每行分别为 October wins! 或 Roy wins!。
【输入样例】
3
4
9
14
【输出样例】
October wins!
October wins!
October wins!
【数据范围】
对于 30% 的数据，1≤n≤30；
对于 60% 的数据，1≤n≤10^6；
对于 100% 的数据，1≤n≤5×10^7, 1≤T≤10^5。
【算法分析】
● 巴什博弈（Bash game）是一种涉及 2 名玩家的双人博弈，属于公平组合游戏（ICG）的典型例子。 博弈中有一堆总数为 n 的物品，2 名玩家轮流从中拿取物品，每次至少拿 1 件，至多拿 m 件，不能不拿，最终将物品拿完者获胜。
（1）n≤m 时，由于一次最少拿一个，最多拿 m 个，甲可以一次拿完，先手赢。
（2）n=m+1 时，无论甲拿走多少个 （1~m 个），剩下的都多于 1 个且少于或等于 m 个，乙都能一次拿走剩余的石子，后手取胜。
● Bash 博弈胜负判定（每次取 1～m 个，取走最后一个石子的胜）
（1）如果n%(m+1) == 0，即 n 是 m+1 的整数倍，那么不管甲拿多少（记作 k，其中 1≤k≤m），乙都拿 m+1-k 个，使剩下的永远是 m+1 的整数倍，直到最后的 m+1 个，所以后拿的乙一定赢（后手赢）。
（2）如果n%(m+1) != 0，即 n 不是 m+1 的整数倍，还有余数 r，那么甲拿走 r 个，剩下的是 m+1 的倍数，这样就转移到了情况（1），相当于甲乙互换，结果是先拿的甲赢（先手赢）。
● 结合巴什博弈的核心范式来看，每次至少拿 1 件，至多拿 m 件，不能不拿，其本质是以 M=m+1 作为模数来划分胜负态。具体而言，当石子总数为 M 的倍数时，该局面属于必败态。此时，处在必败态的玩家，无论进行哪一种合法操作，局面都必然会脱离 M 的倍数；反之，处于必胜态的玩家，则总能通过一步操作，将局面重新拉回 M 的倍数。
● 本题中，所有质数幂 p^k 模 6 的余数均属于 {1,2,3,4,5}，这意味着玩家无法一次取走 6 的倍数颗石子。于是：
（1）若石子总数为 6 的倍数，则无论玩家如何操作，剩余石子数必然不再是 6 的倍数；
（2）反之，若石子总数并非 6 的倍数，先手总能取走与当前余数相对应的质数幂颗石子，从而将剩余石子数修正为 6 的倍数并交给对手。
由此可见，整套博弈逻辑完全符合巴什博弈的胜负判定规则，因此本题可视为模数 M=6 的变形巴什博弈。
【算法代码】
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n,T; cin>>T; while(T--) { cin>>n; if(n%6!=0) cout<<"October wins!\n"; else cout<<"Roy wins!\n"; } return 0; } /* in: 3 4 9 14 out: October wins! October wins! October wins! */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/163572528
https://blog.csdn.net/hnjzsyjyj/article/details/158802453