1025.Divisor Game

Tags: Math Dynamic Programming

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

---

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number N on the chalkboard. On each player's turn, that player makes a move consisting of:

• Choosing any x with 0 < x < N and N % x == 0.
• Replacing the number N on the chalkboard with N - x.

Also, if a player cannot make a move, they lose the game.

Return True if and only if Alice wins the game, assuming both players play optimally.

Example 1:

Input: 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.

Example 2:

Input: 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

Note:

1. 1 <= N <= 1000

---

这道题目第一眼觉得是动态规划的模型，时间复杂度是$O(n^2)$，也就是当前必胜的策略是目前的数字减去其自身的一个因子后必输的情况。

class Solution {
public:
    bool divisorGame(int N) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<bool> d(N + 1, false);
        for (int i = 2; i <= N; ++i) {
            if (isPrime(i)) d[i] = !d[i - 1];
            else {
                for (int j = i - 1; j >= 1; --j) {
                    if (i % j == 0 && !d[i - j]) {
                        d[i] = true; break;
                    }
                }
            }
        }

        return d[N];
    }

    bool isPrime(int n)
    {
        if (n == 2) return true;
        if (!(n & 1)) return false;

        int limit = sqrt(n) + 1;
        for (int i = 3; i <= limit; i += 2) {
            if (n % i == 0) return false;
        }

        return true;
    }
};

但是其实本题存在$O(1)$的解法，不妨列出前9个数字：

1 false
2 true
3 false
4 true
5 false
6 true
7 false
8 true
9 false

可以发现true和false是交错产生的，偶数的情况一定是true，奇数的情况一定是false，这个其实很容易证明，利用数学归纳法证明，当k = 1, 2时显然成立，假设当k时成立，那么当k + 1是奇数的时候，奇数的因子肯定都是奇数，所以奇数减去一个奇数结果是偶数，这个偶数一定小于k + 1，显然是必胜的，则导致k + 1是奇数的情况必输；当k + 1是偶数的时候，此时先手获胜的方法是先取因子1，这样对面先手就是奇数必输，所以得到偶数的情况下先手必胜。所以只需要判断奇偶即可。

class Solution {
public:
    bool divisorGame(int N) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        return !(N & 1);
    }
};