# 1025. Divisor Game 除数博弈

@TOC

## # 题目描述

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:

1. Choosing any `x` with `0 < x < N` and `N % x == 0`.
2. 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 <= N <= 1000

## # 解题方法

### # 找规律

1. 奇数的因子只有奇数，偶数的因子至少一个偶数2
2. 奇数 - 奇数 = 偶数
3. 当Alice的值是N时必输，则当Alice的值是N+1时必赢(拿1即可)

C++代码如下：

``````class Solution {
public:
bool divisorGame(int N) {
return N % 2 == 0;
}
};
``````

### # 动态规划

C++代码如下：

``````class Solution {
public:
bool divisorGame(int N) {
if (N == 1) return false;
if (N == 2) return true;
vector<bool> dp(N, false);
dp[1] = true;
for (int i = 3; i <= N; ++i) {
for (int j = 1; j < i; ++j) {
if (i % j == 0 && !dp[i - j - 1]) {
dp[i - 1] = true;
break;
}
}
}
return dp[N - 1];
}
};
``````

## # 日期

2019 年 8 月 30 日 —— 赶在月底做个题