1025. 除数博弈

Posted on | In
Words count in article: 341 | Reading time ≈ 1

题目

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

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

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

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

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

示例1：

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

示例2：

1
2
3
输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

提示：

  • 1 <= N <= 1000

解法

解法一：

数学方法

如果Alice拿到的数是奇数，那么它的约数肯定是奇数，不可能是偶数；那N-X就是偶数，就是到了Bob的时候，就是偶数，那么Bob只要选出1，返回Alice一个N-1，Alice拿到的还是一个奇数。一次类推，等Bob拿到2的时候，Alice就输了。因此，只要拿到奇数，Alice必输。

反之，如果Alice拿到了偶数，那么Bob必输

JAVA

1
2
3
public boolean divisorGame(int N) {
        return N % 2 == 0;
    }
0%