[ARC185A] mod M Game 2

WuMin4 / 2024-10-23 / 原文

[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;
}