题解 | #宿命之间的对决# #博弈# #因数#

牛客46811D - 宿命之间的对决

https://ac.nowcoder.com/acm/contest/46811/D

题意

给出一个正整数 $x(1\le x\le 10^{18})x(1\backslash leq\; x\backslash leq\; 10^\{18\})$，Alice 和 Bob 轮流进行如下操作：

1. 选取原数的一个因子 $pp$
2. 令 $x:=x-px:=x-p$

谁先将 $xx$ 减到 $\le 0\backslash leq0$，谁输。Alice 先手

问谁赢

思路

不难发现，如果双方足够聪明，选择的因子 $pp$ 一定 $\le \backslash leq$ 当前数，最终数字会被正好减到 $00$

前置知识： 奇数的所有因子都是奇数，偶数至少有一个因子是偶数

当原数是奇数

任何数字减去奇数能让奇偶性改变，并且奇数的所有因子都是奇数。所以当原数是奇数时，不可避免地要减奇数次，Alice 必先将原数减为 $\le 0\backslash leq\; 0$，Alice 必败

当原数是偶数

Alice 可以直接减去一个奇数来让 Bob 拿到奇数（必败态给了 Bob），参照上一条，Bob 必败