1025. Divisor Game

题目信息

题号:

1025

难度:

Easy

主题:

双人博弈、因数选择、最优策略

原题:

LeetCode 1025

重点:

每回合必须选择当前数的真因数 x 并把当前数变为 n - x;无法行动者失败,判断 Alice 在双方最优时能否获胜

题目重述

Alice 和 Bob 以正整数 n 开始游戏,Alice 先行动。轮到一名玩家时,必须选择整数 x,满足 0 < x < n 且 n 能被 x 整除,然后把当前数字替换为 n - x。

双方轮流操作;若某位玩家面对当前数字时找不到合法的 x,该玩家立即失败。假设两人都采用最优策略,请返回 Alice 是否能够获胜。

1 <= n <= 1000。

自建示例

首步选择合适因数可以迫使对手失败:

输入:n = 6
输出:true
解释:Alice 可以选择 x = 3,把数字变为 3;Bob 只能选择 1 得到 2;Alice 再选择 1 得到 1,此时 Bob 无法行动。

起始时没有合法操作:

输入:n = 1
输出:false
解释:不存在满足 0 < x < 1 的整数,Alice 在第一回合就无法行动。