1025. Divisor Game¶
题目信息¶
- 题号:
1025
- 难度:
Easy
- 主题:
双人博弈、因数选择、最优策略
- 原题:
- 重点:
每回合必须选择当前数的真因数
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 在第一回合就无法行动。