难度：⭐
题目描述：
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
最初，黑板上有一个数字 $N$ 。在每个玩家的回合，玩家需要执行以下操作：
选出任一 $x$，满足 $0 < x < N$ 且 $N % x == 0$ 。
用 $N - x $替换黑板上的数字 $N$ 。
如果玩家无法执行这些操作，就会输掉游戏。
只有在爱丽丝在游戏中取得胜利时才返回 $True$，否则返回 $False$。假设两个玩家都以最佳状态参与游戏。
示例1：
1 | 输入：2 |
示例2：
1 | 输入：3 |
提示：
1 <= N <= 1000
解题过程：
思路：
两个玩家都是最佳状态,也就是说两个玩家每次选择都是最优解,只有这样才可能给定一个数字就有一个固定的结局.考虑游戏的结束条件,最后一次选择成功面临的N一定是2,只有为2然后玩家选择了1对方就会输.也就是说最后谁抢到了2谁赢.
- 如果开局N为偶数,那么先手可以选择1,然后后手就要面临奇数N,无论后手怎么选择,先手下一次面临的N还是偶数,那么先手只要继续选择1就可以一直保证N为偶数时选择直到最后一回合面临2然后赢到比赛.
- 如果开局N为奇数,因为奇数不可能有偶数因子,所以奇数(N)-奇数(x)=偶数(后手N),那么一定时后手赢下比赛.
也就是说只要判断N是否是偶数,是偶数先手必赢返回true,是奇数后手必赢返回奇数.
c++代码：(执行用时0ms，击败100.00%，内存消耗6.1M，击败32.56%）
1 | class Solution { |
官方题解:
方法一：找规律
思路与算法
博弈类的问题常常让我们摸不着头脑。当我们没有解题思路的时候，不妨试着写几项试试：
- $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 拿 $1$，根据 $N=3$ 的结论，Bob 会失败，Alice 会获胜。
- $N = 5$的时候，Alice 只能拿 $1$，根据 $N = 4$的结论，Alice 会失败。
- ……
写到这里，也许你有了一些猜想。没关系，请大胆地猜想，在这种情况下大胆地猜想是 AC 的第一步。也许你会发现这样一个现象：N 为奇数的时候 Alice（先手）必败，N 为偶数的时候 Alice 必胜。 这个猜想是否正确呢？下面我们来想办法证明它。
证明
$N = 1$ 和 $N = 2$ 时结论成立。
N > 2 时，假设 $N \leq k$ 时该结论成立，则 $N = k + 1$ 时：
如果 $k$ 为偶数，则 $k + 1$为奇数，x 是 $k + 1$的因数，只可能是奇数，而奇数减去奇数等于偶数，且 $k + 1 - x \leq k$，故轮到 Bob 的时候都是偶数。而根据我们的猜想假设 $N\le k$ 的时候偶数的时候先手必胜，故此时无论 Alice 拿走什么，Bob 都会处于必胜态，所以 Alice 处于必败态。
如果 k为奇数，则 $k + 1$ 为偶数，$x$ 可以是奇数也可以是偶数，若 Alice 减去一个奇数，那么 $k + 1 - x$ 是一个小于等于 $k$ 的奇数，此时 Bob 占有它，处于必败态，则 Alice 处于必胜态。
综上所述，这个猜想是正确的。
下面是代码实现。
c++代码：(执行用时0ms，击败100.00%，内存消耗6.1M，击败32.56%）
1 | class Solution { |
复杂度分析
- 时间复杂度：$O(1)$。
- 空间复杂度：$O(1)$。
方法二：递推
思路与算法
在「方法一」中，我们写出了前面几项的答案，在这个过程中我们发现，Alice 处在 $N = k$ 的状态时，他（她）做一步操作，必然使得 Bob 处于 $N = m (m < k)$的状态。因此我们只要看是否存在一个 $m$ 是必败的状态，那么 Alice 直接执行对应的操作让当前的数字变成 $m$，Alice 就必胜了，如果没有任何一个是必败的状态的话，说明 Alice 无论怎么进行操作，最后都会让 Bob 处于必胜的状态，此时 Alice 是必败的。
结合以上我们定义 $f[i]$表示当前数字 $i$ 的时候先手是处于必胜态还是必败态，$\textit{true}$ 表示先手必胜，$\textit{false}$表示先手必败，从前往后递推，根据我们上文的分析，枚举 $i$在 $(0, i)$ 中 $i$ 的因数 $j$，看是否存在 $f[i-j]$为必败态即可。
c++代码：(执行用时4ms，击败34.29%，内存消耗6.6M，击败5.05%）
1 | class Solution { |
复杂度分析
- 时间复杂度：$O(n^2)$。递推的时候一共有 $n$ 个状态要计算，每个状态需要 $O(n)$ 的时间枚举因数，因此总时间复杂度为 $O(n^2)$。
- 空间复杂度：$O(n)$。我们需要 $O(n)$ 的空间存储递推数组 $f$ 的值。
总结：
官方题解和我的思路一毛一样，得意😜，这不双百？？我真的觉得是击败的比例，其他的都是和我一样的。。。
方法一给出了归纳法证明猜想，我是直接叙述的（学术水平不到位，讲不出来。。。），方法二递推没咋看，效率也不高，累了，溜了溜了。。。
