质数取石子游戏【牛客tracker 每日一题】

质数取石子游戏时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述A l i c e AliceAlice和B o b BobBob正在玩一个取石子游戏游戏规则如下有n nn个石子堆在一起A l i c e AliceAlice和B o b BobBob轮流从中取1 11个或任意质数个石子取石子的数量不能超过当前剩余石子数也不能不取谁取走最后一个石子谁就赢了。A l i c e AliceAlice想知道如果自己先手且自己和B o b BobBob都采取最优策略最终谁能获胜输入描述本题包含多组测试数据。第一行输入一个正整数T 1 ≦ T ≦ 10 3 T1≦T≦10^3T1≦T≦103表示数据组数。接下来对于每组测试数据输入一行一个正整数n 1 ≦ n ≦ 10 9 n1≦n≦10^9n1≦n≦109表示初始时石子的数量。输出描述输出共T TT行每行一个字符串。如果A l i c e AliceAlice在最优策略下能够赢得游戏请输出A l i c e AliceAlice否则输出B o b BobBob。示例1输入6 1 2 3 4 10 10000输出Alice Alice Alice Bob Alice Bob解题思路本题属于组合博弈必败态推导问题通过分析取石子规则的数论性质可直接得到胜负判定的简洁规律。取石子规则为每次可取1个或任意质数个。结合数论性质分析除2外所有质数均为奇数因此可取的石子数只有奇数和2两类。通过小范围枚举推导必败态当前玩家必输的局面n 4 n4n4是最小的必败态无论取1、2、3个剩余石子数均为对手的必胜态。进一步可证所有4的倍数都是必败态。若当前石子数是4的倍数无论取1、2还是奇质数对手都可以通过取对应数量1、3或2将石子数重新拉回4的倍数最终让先手面对0石子的败局。反之若石子数不是4的倍数余数为1时取1个、余数为2时取2个、余数为3时取3个均可让对手面对4的倍数的必败态因此先手必胜。最终结论若n nn是4的倍数先手Alice必败否则Alice必胜。每组查询仅需一次取模运算时间复杂度O ( 1 ) O(1)O(1)完美适配n ≤ 10 9 n \le 10^9n≤109、T ≤ 10 3 T \le 10^3T≤103的数据约束。总结核心逻辑通过分析取数的奇偶性与模4性质推导得出4的倍数为必败态其余均为必胜态。关键操作对每组数据计算n m o d 4 n \bmod 4nmod4根据结果直接判定胜负。效率保障纯常数级运算无预处理与循环开销轻松应对超大数值与千级查询量。代码简要说明输入处理读取测试用例组数T TT逐组读取石子数n nn。胜负判定通过n 3等价于对4取模快速判断余数余数非0则Alice获胜余数为0则Bob获胜。输出优化关闭同步流提升输入输出效率每组结果直接输出对应字符串。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intT;cinT;while(T--){intn;cinn;cout(n3?Alice\n:Bob\n);}return0;}