素数博弈

算法思路

将 $n$ 分解为

记 $C=e_{1}+e_{2}+\cdots+e_{k}$，即包含重复次数的素因子总数。

每次操作恰好移除一个素因子，因此无论双方如何选择，游戏都恰好进行 $C$ 次操作。

Alice 进行第 $1,3,5,\ldots$ 次操作，Bob 进行第 $2,4,6,\ldots$ 次操作。因此：

• 若 $C$ 为奇数，Alice 完成最后一次操作，输出 Alice；

• 若 $C$ 为偶数，输出 Bob。

实现时，先筛出不超过 $10^{4}$ 的所有素数。对于每组数据，令 $x=n$，依次用素数 $p$ 试除： 只要 $p$ 整除 $x$，就令 $x$ 除以 $p$，并将 $C$ 加 $1$。 当 $p^{2}>x$ 时停止；若此时 $x>1$，则剩余的 $x$ 是一个素数，将 $C$ 再加 $1$。

注意，素因子需要重复计算。例如 $12=2^{2}\cdot 3$，因此 $C=3$。 当 $n=1$ 时，$C=0$，输出 Bob。

正确性证明

根据唯一分解定理，每次除以一个素数，都会使素因子总数恰好减少 $1$。 当且仅当素因子总数变为 $0$ 时，黑板上的数变为 $1$，游戏结束。 因此，游戏的操作次数恒为初始的 $C$。

若 $C$ 为奇数，最后一次操作由 Alice 完成；若 $C$ 为偶数，Alice 无法获胜。 算法通过素因数分解正确统计 $C$，并根据其奇偶性判断胜者，因此算法正确。

复杂度分析

设 $N=10^{8}$ 为 $n$ 的上界，$L=\sqrt{N}=10^{4}$，$P$ 为不超过 $L$ 的素数个数。

使用埃氏筛预处理的时间复杂度为 $O(L\log\log L)$， 每组试除分解的时间复杂度为 $O(P+\log N)$。 因此，总时间复杂度为

空间复杂度为 $O(L)$。