除数博弈-c语言

除数博弈

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 n 。在每个玩家的回合，玩家需要执行以下操作：

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

如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 true 。假设两个玩家都以最佳状态参与游戏。

示例 1：

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

示例 2：

输入：n = 3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
题解：
博弈类的问题常常让我们摸不着头脑。当我们没有解题思路的时候，不妨试着写几项试试：

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

写到这里，也许你有了一些猜想。没关系，请大胆地猜想，在这种情况下大胆地猜想是 AC 的第一步。也许你会发现这样一个现象：nnn 为奇数的时候 Alice\text{Alice}Alice（先手）必败，nnn 为偶数的时候 Alice\text{Alice}Alice 必胜。 这个猜想是否正确呢？下面我们来想办法证明它。

证明

n=1n = 1n=1 和 n=2n = 2n=2 时结论成立。

n>2n > 2n>2 时，假设 n≤kn \leq kn≤k 时该结论成立，则 n=k+1n = k + 1n=k+1 时：
    如果 kkk 为偶数，则 k+1k + 1k+1 为奇数，xxx 是 k+1k + 1k+1 的因数，只可能是奇数，而奇数减去奇数等于偶数，且 k+1−x≤kk + 1 - x \leq kk+1−x≤k，故轮到 Bob\text{Bob}Bob 的时候都是偶数。而根据我们的猜想假设 n≤kn\le kn≤k 的时候偶数的时候先手必胜，故此时无论 Alice\text{Alice}Alice 拿走什么，Bob\text{Bob}Bob 都会处于必胜态，所以 Alice\text{Alice}Alice 处于必败态。
    如果 kkk 为奇数，则 k+1k + 1k+1 为偶数，xxx 可以是奇数也可以是偶数，若 Alice\text{Alice}Alice 减去一个奇数，那么 k+1−xk + 1 - xk+1−x 是一个小于等于 kkk 的奇数，此时 Bob\text{Bob}Bob 占有它，处于必败态，则 Alice\text{Alice}Alice 处于必胜态。

综上所述，这个猜想是正确的。
代码：

bool divisorGame(int n){
 return n%2==0;
}