# 1025. 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`

{% hint style="info" %}
觀察一下N = 1\~4的情況，再由數學歸納法可以得知N是Odd時，玩家會輸，N是even時，玩家會獲勝。\
N = 1, 玩家輸。\
N = 2, 玩家贏。\
N = 3, 玩家輸。\
N = 4, 玩家贏。\
假設N = 2k時，玩家贏，N = 2k + 1時，玩家輸。\
(i) N = 2k, 該數可以有odd或者even的因數，這裡用odd\_0和even\_0表示。如果玩家選擇odd\_0，那剩下的數N'為N - odd\_0，為一個奇數。N'所有的因數都是奇數，這裡用odd\_1表示。那麼f(N) = f(2k) = f(2k - odd\_0 - odd\_1) = f(even) = true。\
(ii) N = 2k + 1, 該數只有odd的因數，這裡用odd\_0表示。那麼N' = N - odd\_0為一個偶數。N'可以有odd和even的因數，這裡用odd\_1和even\_1表示，這題假設大家都是聰明人，每次動作都是對自己最有利的，那麼對手會選擇odd\_1，好讓留給玩家的是奇數。f(N) = f(2k + 1) = f(2k + 1 - odd\_0 - odd\_1) = f(odd) = false。
{% endhint %}

```cpp
// Math
bool divisorGame(int N) {
    return N % 2 == 0;
}
```

{% hint style="info" %}
可以利用Top-Down Recursion搭配memoization dp array去紀錄已經算過的結果避免重複。
{% endhint %}

```cpp
// Top-Down Recursive DP
bool helper(int N, vector<int>& dp, bool res) {
    if (dp[N] != 0) return dp[N] == 1;
    for (int i = 1; !res && i * i < N; ++i) {
        if (N % i == 0) res = !helper(N - i, dp, res);
    }
    dp[N] = res ? 1 : -1;
    return res;
}
bool divisorGame(int N) {
    vector<int> dp(1001, 0);
    return helper(N, dp, false);
}
```

{% hint style="info" %}
由Alice的角度loop所有i的可能，然後從比i小的數字中找出符合的因數j，檢查i - j是否會讓對手輸，如果會讓對手輸的話，Alice就會選這個數，然後再一直下去。
{% endhint %}

```cpp
// Bottom-Up DP
bool divisorGame(int N) { // time: O(N^2); space: O(N)
    vector<bool> dp(N + 1, false);
    for (int i = 2; i <= N; ++i) {
        for (int j = 1; j < i; ++j) {
            if (i % j == 0) {
                if (!dp[i - j]) { // If Alice chooses i, and will let her opponent lose
                    dp[i] = true;
                    break;
                }
            }
        }
    }
    return dp[N];
}
```