洛谷 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 行~第 T1 行一行一个正整数 n表示石子个数。​​​​​​​【输出格式】T 行每行分别为 October wins! 或 Roy wins!。​​​​​​​【输入样例】34914​​​​​​​【输出样例】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 件不能不拿最终将物品拿完者获胜。1n≤m 时由于一次最少拿一个最多拿 m 个甲可以一次拿完先手赢。2nm1 时无论甲拿走多少个 1~m 个剩下的都多于 1 个且少于或等于 m 个乙都能一次拿走剩余的石子后手取胜。● Bash 博弈胜负判定每次取 1m 个取走最后一个石子的胜1如果n%(m1) 0即 n 是 m1 的整数倍那么不管甲拿多少记作 k其中 1≤k≤m乙都拿 m1-k 个使剩下的永远是 m1 的整数倍直到最后的 m1 个所以后拿的乙一定赢后手赢。2如果n%(m1) ! 0即 n 不是 m1 的整数倍还有余数 r那么甲拿走 r 个剩下的是 m1 的倍数这样就转移到了情况1相当于甲乙互换结果是先拿的甲赢先手赢。● 结合巴什博弈的核心范式来看每次至少拿 1 件至多拿 m 件不能不拿其本质是以 Mm1 作为模数来划分胜负态。具体而言当石子总数为 M 的倍数时该局面属于必败态。此时处在必败态的玩家无论进行哪一种合法操作局面都必然会脱离 M 的倍数反之处于必胜态的玩家则总能通过一步操作将局面重新拉回 M 的倍数。● 本题中所有质数幂 p^k 模 6 的余数均属于 {1,2,3,4,5}这意味着玩家无法一次取走 6 的倍数颗石子。于是1若石子总数为 6 的倍数则无论玩家如何操作剩余石子数必然不再是 6 的倍数2反之若石子总数并非 6 的倍数先手总能取走与当前余数相对应的质数幂颗石子从而将剩余石子数修正为 6 的倍数并交给对手。由此可见整套博弈逻辑完全符合巴什博弈的胜负判定规则因此本题可视为模数 M6 的变形巴什博弈。【算法代码】#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n,T; cinT; while(T--) { cinn; if(n%6!0) coutOctober wins!\n; else coutRoy wins!\n; } return 0; } /* in: 3 4 9 14 out: October wins! October wins! October wins! */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/163572528https://blog.csdn.net/hnjzsyjyj/article/details/158802453