质数取石子游戏
时间限制：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 ） T（1≦T≦10^3）T（1≦T≦103），表示数据组数。
接下来对于每组测试数据，输入一行一个正整数n （ 1 ≦ n ≦ 10 9 ） n（1≦n≦10^9）n（1≦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 n=4n=4是最小的必败态：无论取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获胜。 - 输出优化：关闭同步流提升输入输出效率，每组结果直接输出对应字符串。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intT;cin>>T;while(T--){intn;cin>>n;cout<<(n&3?"Alice\n":"Bob\n");}return0;}
