[ARC185A] mod M Game 2
题意
Alice 和 Bob 每人手里有 \(n\) 张牌，牌上有数字 \(1,2,\cdots,n\)，从 Alice 开始轮流出牌，若一个人出牌后场上牌数字的总和能被 \(m\) 整除，则这个人输掉，若两人的牌都出完后还没有人输，则 Alice 获胜。
给出 \(n,m\pod{n<m}\)，问两人都进行最优操作后谁会赢。
思路
显然若一个玩家手中牌的数量 \(\ge2\)，那么他出牌后一定不会输。因为 \(n<m\)，所以不存在两张数字为 \(x,y \pod{x\neq y}\) 的牌使得 \(x,y\equiv 0\pmod{m}\)，两张以上同理，由此我们可以知道输赢的关键就在 Alice 和 Bob 只剩一张牌的时候。
因为 Alice 先手，所以两人只剩一张牌时是 Alice 先出。Alice 出完牌后，场上的牌的数字和即为 \(n\times(n+1)-x\)，其中 \(x\) 即为 Bob 最后一张牌的数字。Bob 如果想赢，则需要 \(n\times(n+1)-x\equiv 0\pmod m\)，即 \(x=(n\times(n+1))\bmod m\)。
那么 Alice 是否可以使 Bob 不剩下数字为 \(x\) 的牌呢？若 Alice 出完倒数第二张牌后剩下一张数字为 \(y\) 的牌，则 Bob 打出一张牌后场上的牌的数字和为 \(n\times (n+1)-x-y\)，因为 \(n\times(n+1)-x\equiv 0\pmod m\) 且 \(1\le y\le n\)，所以 \(n\times (n+1)-x-y\equiv 0\pmod m\) 不会成立。
因为牌的数字为 \(1,2,\cdots,n\)，所以当 \(1\le x\le n\) 时，Bob 获胜，否则牌会全部出完，Alice 获胜。
代码
#include<bits/stdc++.h>
using namespace std;
int T;
long long n,m;
signed main(){
ios::sync_with_stdio(false);
cin.tie(),cout.tie();
cin>>T;
while(T--){
cin>>n>>m;
cout<<(n*(n+1)%m==0?"Alice":(n*(n+1)%m<=n?"Bob":"Alice"))<<endl;
}
return 0;
}