题解 - Alice

标题形貌

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，直到变为“非两个偶数”的情况，再根据必胜状态和必败状态判定即可。
代码

[code][/code]
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金