今日题目
T1025 除数博弈
题目描述
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N – x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。
示例 1：
输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。
示例 2：
输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
提示：
1 <= N <= 1000
标签
博弈
解析
本题的唯一问题是如何通过数字判断胜利条件。显然对于任意奇数N，如果N是素数，则x只能取1，N-x为偶数；如果N是合数，由N是奇数，可知N的因子都是奇数，即x只能取奇数，N-x为偶数。总之，N是奇数时，N-x一定是偶数。
那么，如果N是偶数呢？这时我们有两种选择：N-x是奇数，或N-x是偶数。通过上一段我们可以看出，如果N-x是奇数，则再次轮到我们操作时，N一定是偶数。但如果N-x是偶数，这个选择的权利就交到了对方手上。另外，从示例中也可以看出，N=2时我们是必胜的。
既然N=2是必胜的，那么接下来的关键，就变成了，如何将N>2的情况，转化成N=2的情况。
对于N是偶数的情况，如果我们令N-x为奇数，则N经过两次减法、再次轮到我们操作时，一定还是偶数。这样下去，一定可以得到N=2的情况，此时我们必败。
对于N是奇数的情况，N-x只能为偶数，此时等同于对方N为偶数的情况，此时我们必败。
因此，只需要通过判断N是奇数还是偶数，就可以得到正确的结果。
当然，如果追求更短的用时，你甚至可以使用位运算。显然N为偶数时二进制的最后一位必为0，此时需要返回True，而N为奇数时二进制的最后一位为1，返回False。使用位运算时，我们只需要返回not(N&1)即可。
C++解法
class Solution {
public:
bool divisorGame(int N) {
if(N%2)
{
return false;
}
else
{
return true;
}
}
};
python解法
class Solution:
def divisorGame(self, N: int) -> bool:
return not (N & 1)
备注
耐心分析很重要