除数博弈.md

除数博弈

爱丽丝和鲍勃一起玩游戏，他们轮流行动，爱丽丝先手开局。
最初，黑板上有一个数字N，在每个玩家的回合，玩家需要执行以下操作：

• 选出任一x，满足0 < x < N且N % x == 0。
• 用N - x替换黑板上的数字N。

如果玩家无法执行这些操作，就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回true，否则返回false，假设两个玩家都以最佳状态参与游戏。

示例

输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。

输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

题解

/**
 * @param {number} N
 * @return {boolean}
 */
var divisorGame = function(n) {
    return n & 1 ? false : true;
};

思路

理解一下题意，查看了输入输出示例，推断这是一个通过判断奇偶性决定胜负的游戏。
这里引用官方推论：博弈类的问题常常让我们摸不着头脑。当我们没有解题思路的时候，不妨试着写几项试试：

• N = 1的时候，区间(0, 1)中没有整数是 n的因数，所以此时Alice败。
• N = 2的时候，Alice只能拿1，N变成1，Bob无法继续操作，故Alice胜。
• N = 3的时候，Alice只能拿1，N变成2，根据N = 2的结论，我们知道此时Bob 会获胜，Alice败。
• N = 4的时候，Alice能拿1或2，如果Alice拿1，根据N = 3的结论，Bob会失败，Alice会获胜。
• N = 5的时候，Alice只能拿11，根据N = 4的结论，Alice会失败。
• ......

写到这里，也许你有了一些猜想。没关系，请大胆地猜想，在这种情况下大胆地猜想是AC的第一步。也许你会发现这样一个现象：N为奇数的时候Alice（先手）必败，N为偶数的时候 Alice必胜。 这个猜想是否正确呢？下面我们来想办法证明它。
证明：N = 1和N = 2时结论成立。
N > 2时，假设N ≤ k时该结论成立，则N = k + 1时，如果k为偶数，则k + 1为奇数，x是k + 1的因数，只可能是奇数，而奇数减去奇数等于偶数，且k+1−x≤k，故轮到Bob的时候都是偶数。而根据我们的猜想假设N≤k的时候偶数的时候先手必胜，故此时无论Alice拿走什么，Bob都会处于必胜态，所以Alice处于必败态。如果kk为奇数，则k + 1为偶数，x可以是奇数也可以是偶数，若Alice减去一个奇数，那么k+1−x是一个小于等于k的奇数，此时Bob占有它，处于必败态，则Alice处于必胜态。综上所述，这个猜想是正确的。

每日一题

https://github.com/WindrunnerMax/EveryDay

参考

https://leetcode-cn.com/problems/divisor-game