AGC010D [AGC010D] Decrementing

题意：给出 个整数。第 个整数是 ，它们的最大公约数为 。

A 和 B 进行博弈。A 为先手，他们将轮流进行以下操作（以下两步相当于一次操作）：

• 选择黑板中大于 的一个数，将其减 。

• 此后，将黑板上所有数全部除以所有数的最大公约数。

不能再进行操作的人失败。两人都选择最好的方式行动，请求出谁会最终胜利。

，，时限 。

---

加减法和 搞一块，有点神必，应该不至于是大型性质题。先莽一些特殊情况。

不难发现，若数字中存在 ，那么公因数总是 ，操作的第二部就无影响了。

接下来就是两人轮流给所有数减一，若有奇数个偶数，先手必胜，否则必败。

我们发现“减一”这个操作不能跨越奇偶性，于是顺着这个思路继续扩展。

• 若有奇数个偶数，则先手必胜。（由于开始时互质，必然至少有一个奇数）

具体方法：归纳证明。先手面对有奇数个偶数，且至少有一个奇数的局面。

先手操作一个偶数，使其变为奇数，若仍存在偶数，公因数仍然为 ，否则公因数可能不为 ，但所引发的操作不会影响偶数个数（因为本来就没有偶数了）。

此时后手有偶数个偶数，和至少两个奇数。无论如何操作，都会产生奇数个偶数，且公因数必定为 。

而终止态没有偶数，游戏一定会结束，故后手一定会得到终止态，后手必败。

• 若有偶数个偶数，且有大于一个奇数，后手必胜。

  先手无论如何操作，都只会把“有奇数个偶数，且至少有一个奇数”的必胜局面送给后手。

此外，若只有一个奇数，先手只能操作这个奇数（否则必败），然后使得所有数除以 。若该数已经为 ，先手必败。

不可能没有奇数。

这最多持续 次，于是复杂度为 。