lc1025-除数博弈

题目描述

• 爱丽丝先手
• 初始数 n (1 <= n <= 1000)
• 若能选出 x (0 < x < n) 使 x 能整除 n，则 n 变为 n-x
• 若不能，则输掉

示例

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

输入：n = 3
输出：false
解释：爱丽丝选择 1（n 变为 2），鲍勃也选择 1（n 变为 1），然后爱丽丝无法进行操作

题解

• 思路

从 1 开始反推几个数
n: 1 2 3 4 5 6 ...F T F T F T
模拟的话，找出 n 的因子，遍历可能的情况，若能走到前面的必败态，则当前为必胜态
但这是简单题，不太可能这样做
只能猜结论，然后证明

结论：奇数必败，偶数必胜证明（数学归纳法）：
边界：n=1，奇数，败
假设 k < n 时(n>1)，结论成立
只需证 k = n 时结论成立
若 k 为奇数，当 x|k 时，x 必为奇数，k-x 必为偶数，那么操作完对手来到必胜态
若 k 为偶数，1 必满足 1|k，k-1 为奇数，操作完对手来到必败态
奇偶均满足结论，得证

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