题目描述
Alice 和 Bob 在玩游戏,游戏规则如下:
- 有两堆石子,每堆石子有非负整数个
- Alice 与 Bob 轮流操作,Alice 先手,每次可以从任意一堆石子中取出若干个
- 取出的石子个数应满足为另一堆石子个数的因数(此处规定任何数均为0的因数)
- 将石子取完的玩家获胜
给定一个初始状态,现在请判断,在 Alice,Bob 均采用最佳策略时,最后谁将获胜
输入
第一行一个非负整数 T 表示接下来有 T 种需进行判断的状态.
接下来 T 行,每行两个非负整数,表示两堆石子的数量 n1,n2.
输出
共 T 行,第 i 行一个字母 A 或 B,A 表示 Alice 将会赢得游戏,B 表示 Bob 将会赢得游戏.
样例
样例输入
4
1 4
5 5
1 1
2 5
样例输出
A
B
B
A
提示
对于所有数据: 0≤T≤1e6,0≤n1,n2≤1e9,n1,n2 不同时为 0.
对于测试点 1,2: n1,n2≤5.
对于测试点 3,4: n1,n2≤1000.
对于测试点 5,6: n1,n2 互质.
分析
简单思维题。
因为任何数均为0的因数，所以我们可以得出一个结论：当场上存在0时，直接把另外一堆拿空，游戏结束，当前回合操作者获胜！
必败状态：两个奇数。
证明：假设Alice目前面临的状态为两个奇数，由于奇数的因子只有奇数，所以Alice操作后状态一定变为一奇一偶，那么Bob可以通过将偶数减去1，使得状态再次变为两个奇数，故Alice将始终面临两个奇数的状态，最终在Alice某次操作后，会把其中一个奇数变为0，此时Bob获胜。
必胜状态：一奇一偶。
证明：可以通过将偶数减去1，使得状态变为两个奇数。
再考虑两个偶数的情况：
对于两个偶数，谁都不会去把一个数变成奇数，因此拿走的数都是偶数，即所有操作建立在2的倍数上。
因此我们可以对n和m不断除2，直到变为“非两个偶数”的情况，再根据必胜状态和必败状态判断即可。
代码
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int n,m;
void solve(){
cin >> n >> m;
if(n % 2 && m % 2) cout << "B\n";
else if(!(n % 2 == 0 && m % 2 == 0)) cout << "A\n";
else{
while(n % 2 == 0 && m % 2 == 0) n /= 2,m /= 2;
if(n % 2 && m % 2) cout << "B\n";
else cout << "A\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}