[??记录]AT2305 [AGC010D] Decrementing

**题意** ：给出 $n$ 个整数。第 $i$ 个整数是 $A_i$ ，它们的最大公约数为 $1$ 。 A 和 B 进行博弈。A 为先手，他们将轮流进行以下操作（以下两步相当于一次操作）： - 选择黑板中大于 $1$ 的一个数，将其减 $1$。 - 此后，将黑板上所有数全部除以所有数的最大公约数。 不能再进行操作的人失败。两人都选择最好的方式行动，请求出谁会最终胜利。 $n\leq 10^5,a_i\leq 10^9$ ，时限$\texttt{2s}$。 ------------ 加减法和 $\rm gcd$ 搞一块，有点神必，应该不至于是大型性质题。先莽一些特殊情况。 不难发现，若数字中存在 $1$ ，那么公因数总是 $1$ ，操作的第二部就无影响了。 接下来就是两人轮流给所有数减一，若有奇数个偶数，先手必胜，否则必败。 我们发现“减一”这个操作不能跨越奇偶性，于是顺着这个思路继续扩展。 - 若有奇数个偶数，则先手必胜。（由于开始时互质，必然至少有一个奇数） 具体方法 ： 归纳证明。先手面对有奇数个偶数，且至少有一个奇数的局面。 先手操作一个偶数，使其变为奇数，若仍存在偶数，公因数仍然为 $1$，否则公因数可能不为 $1$ ，但所引发的操作不会影响偶数个数（因为本来就没有偶数了）。 此时后手有偶数个偶数，和至少两个奇数。无论如何操作，都会产生奇数个偶数，且公因数必定为 $1$。 而终止态没有偶数，游戏一定会结束，故后手一定会得到终止态，后手必败。 - 若有偶数个偶数，且有**大于一个**奇数，后手必胜。 先手无论如何操作，都只会把“有奇数个偶数，且至少有一个奇数”的必胜局面送给后手。 此外，若只有一个奇数，先手只能操作这个奇数（否则必败），然后使得所有数除以 $\gcd$。若该数已经为 $1$ ，先手必败。 不可能没有奇数。 这最多持续 $O(\log a)$ 次，于是复杂度为 $O(n\log a)$。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 100500 using namespace std; int gcd(int a,int b) {return !b ? a : gcd(b,a%b);} bool solve(int *a,int n) { int c0=0,c1=0; for (int i=1;i<=n;i++) if (a[i]&1)c1++; else c0++; if (c0&1)return 1; if (!(c0&1)&&c1>2)return 0; for (int i=1;i<=n;i++) if (a[i]&1) if (a[i]>1)a[i]--; else return 0; int d=0; for (int i=1;i<=n;i++)d=gcd(a[i],d); for (int i=1;i<=n;i++)a[i]/=d; return !solve(a,n); } int n,a[MaxN]; int main() { scanf("%d",&n); for (int i=1;i<=n;i++)scanf("%d",&a[i]); puts(solve(a,n) ? "First" : "Second"); return 0; } ```