自动搬运

查看原文

来自洛谷，原作者为

	Ethan104 Bon Voyage.

搬运于2025-08-24 23:11:13，当前版本为作者最后更新于2024-07-17 08:39:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，容易发现的是一二操作的描述都是故弄玄虚的。一操作中实际上除掉的是哪个质因子都是无所谓的，而二操作中相当于把质因子的个数加倍，因而若定义 $d_i$ 为 $a_i$ 的质因子数量，则：

• 操作一相当于将某个 $d_i$ 减少 $1$ ；
• 操作二相当于将某个 $d_i$ 乘以 $2$ 。

先看一个子问题：所有 $d_i\ge2$ ，即所有 $a_i$ 不为质数。
先假设二操作不存在。
显而易见的，当所有 $d_i$ 都是偶数时，后手必胜；每次后手只要重复一次先手的操作即可。这是容易理解的，因为每次先手要面对的都是所有 $d_i$ 都是偶数的局面，即先手在操作时的所有 $d_i\ge2$ ，那么先手绝对无法在一步之内获得任何一分，换言之，后手将会拿到所有分数。
其次， $d_i$ 有奇数的情况。在有偶数个 $d_i$ 是奇数时，后手必胜。行动方式是，在先手将某个奇数变为偶数的场合，后手也选择一个奇数变为偶数；在先手将某个偶数变为奇数的场合，后手再对那个 $d_i$ 使用一次操作一。
分析为什么可以胜利：在先手操作前，后手操作后的视角下，先手面前的奇数个数永远都是偶数；而由于初始的 $d_i\ge2$ ，在先手操作一个奇数时先手无法消除这个 $d_i$ ，而由于偶数个 $d_i$ 为奇数，后手总能将一个奇数 $d_i$ 同样转化为偶数。而在先手操作偶数时就和上文一样，因而先手面前的奇数个数一定会逐渐减少，以至于最后会退化成没有奇数的情况，即后手必胜。
那么，有奇数个 $d_i$ 是奇数的情况也是简单的了：先手只要先将某个奇数变为偶数，就相当于退化成了上一种情况，不同的是先后手对换了，则在这种情况下先手必胜。
那么如果将二操作加回来呢？实际上，可以发现在上述三种情况下，胜方都能拿到全部分数：这是因为上面三个方案之所以能胜，都是因为它们胜利的基础都在于不让输方拿到一分，而在这种情况下，输方无法使用二操作，而赢方无需使用二操作便能获胜，即二操作相当于不存在，对上述结论无影响。

下面是有 $d_i=1$ 的情况。
先考虑一下二操作的意义，发现上文中胜利条件只和所有 $d_i$ 的奇偶有关，一操作相当于反转一个数的奇偶，那么二操作在操作一个偶数 $d_i$ 时相当于场上所有数的奇偶无变化，从上文中可以看出这样相当于空过自己的回合，即相当于反转了一次双方的先后手，即在所有 $d_i\ge2$ 时，二操作能反转双方胜负。
对初始时有 $d_i=1$ 的情况时，双方的最优策略都是优先消除这些 $d_i$ 。原因是，在这种情况下双方都能轻易得分，但其他方式的得分效率都不如直接消除为 $1$ 的 $d_i$ ；要快速得分的原因在于可以获得二操作的使用次数，而“反转双方胜负”这个操作的可使用次数若大于对方可发现是一定胜利的。
在上述阶段结束之后，场上的 $d_i\ge2$ 。若是初始 $d_i=1$ 的个数为奇数，先手会获得更多次使用二操作的权利，即一定获胜；而在双方分数相等情况下，则仍按 $d_i\ge2$ 的方式处理，因为在此种情况下任何一边反转胜负时对方一定有机会将其反转回来。
但是二操作能反转双方胜负的条件当且仅当有 $d_i$ 是偶数。容易发现，这个条件一定能达成，在最后所有 $d_i\ge2$ 的情况下，使用操作一时一定有一个时刻 $d_i=2$ ，此时使用操作二就能保证有效。
特别地，在所有 $d_i=1$ 时，若 $n$ 为偶数，平局；否则，先手必胜。
于是就做完啦。