Leetcode 1025. 除数博弈

题目描述

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：

• 选出任一 x，满足 0 < x < N 且 N % x == 0 。
• 用 N - x 替换黑板上的数字 N 。

如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。

示例 1:

输入：2

输出：true

解释：爱丽丝选择 1，鲍勃无法进行操作。

示例 2:

输入：3

输出：false

解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

最佳状态是指，数字若减去其任一除数因子对于对方为 false，则当前数字返回 true，否则当前数字返回 false。

解法

不妨以 f(x) 表示数字为 x 的返回值，则当 x=1 时，f(1) 为 false。

当 x=2，除数因子为 1，因为 f(1)=false，所以 f(2)=true 当 x=3，除数因子为 1，因为 f(2)=true，所以 f(3)=false 当 x=4，除数因子为 1,2，因为 f(3)=false，所以 f(4)=true ...

观察可知，对于前面几个数，若 x 为奇数，则 f(x)=false；若 x 为偶数，则 f(x)=true。

当 x>4，若 x 为奇数，则 x 的除数因子都是奇数，即 x 减去其除数因子皆为偶数，因为偶数的函数值为 true，则 f(x)=false； 当 x>4，若 x 为偶数，因为 x-1 为奇数，因为奇数的函数值为 false，则 f(x)=true；

由此可知，所有奇数的函数返回值为 false，偶数的函数返回值为true。

class Solution:
    def divisorGame(self, N: int) -> bool:
        return N%2==0