除数博弈

1025. 除数博弈

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

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

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

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

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

示例 1：

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

示例 2：

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

提示：

1. 1 <= N <= 1000

我们尝试写几项：

• 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 选择 2 时 根据 N = 2的结论 ，Alice 败，Alice 选择 1 时，根据 N = 3 的结论，Alice 胜。

• N = 5 ，Alice 选择 1 ，根据 N = 4 的结论，Alice 败。

我们定义 f[i] 表示当数字为 i 时，先手处于必胜态还是必败态，true 代表先手胜，false 代表先手败。当 N = i 时，Alice 在 (0, i)中选择一个因数 j ，使得i % j == 0，且 f[i - j] = false（Bob先手必败），那么 Alice 就可获胜。否则 Alice 败。

class Solution {
    public boolean divisorGame(int N) {
        boolean[] f = new boolean[N + 2];
        f[1] = false;
        f[2] = true;
        for(int i = 3; i <= N; i++){
            for(int j = 1; j < i; j++){
                if((i % j == 0) && !f[i - j]){
                    f[i] = true;
                    break;
                }
            }
        }
        return f[N];
    }
}

时间复杂度O(n^2)，空间复杂度O(n)。

看到前面几项的规律，我们猜测 N 为 奇数时 Alice（先手）必败，N 为偶数时，Alice 必胜。

证明：

1. N = 1 和 N = 2 时结论成立。
2. N > 2 时，假设 N <= k 时该结论成立，则 N = k + 1 时：
   • 如果 k 为偶数，则 k + 1 为奇数，x 是 k + 1 的因数，只能为奇数，奇数减去奇数得到偶数，且 k + 1 - x <= k，轮到 Bob 时都是偶数，根据假设，N <= k时，偶数先手必胜，则 Bob 必胜，Alice 必败。
   • 如果 k 为奇数，则 k + 1 为偶数，x 是 k + 1的因数，x 可为奇数和偶数，若 Alice 减去一个奇数，k + 1 - x 一定是个奇数，根据假设 Bob 必败，Alice 必胜。当 x 为偶数时，Alice 必败。故 Alice 选择 x 为奇数。

综上，猜想正确。

class Solution {
    public boolean divisorGame(int N) {
        return (N & 1) == 0;
    }
}

时间复杂度O(1)，空间复杂度O(1)。