【AtCoder Grand Contest 010 D】Decrementing | Mrsrz's blog

博弈论。

题目大意：

给定 $n$ 个整数 $A_1,A_2,A_3,\ldots,A_n$，两人轮流操作，每次操作如下：

• 操作方选择一个大于 $1$ 的数，令其减 $1$。
• 然后令 $d=\gcd\{A_1,A_2,A_3,\ldots,A_n\}$，令所有 $A_i$ 变为 $\frac{A_i}d$。

不能操作者输。

保证一开始所有数的最大公因数为 $1$。

问先手必胜还是后手必胜。

题解：

设 $s=\sum\limits_{i=1}^n A_i$，如果存在一个 $A_i=1$，那么除掉最大公因数的操作就可以忽略。此时，一共能减 $1$ 的次数为 $s-n$，故若 $s-n$ 为奇数则先手胜，否则后手胜。

如果 $\gcd$ 中不存在因子 $2$（即 $\gcd$ 为奇数），则所有数除以 $\gcd$ 后，奇偶性不变。所以我们只关心 $\gcd$ 中存在因子 $2$ 的情况。

我们考虑统计出 $A_i$ 中偶数的个数 $c$，由于保证一开始和每次除完后，$\gcd$ 都为 $1$。所以 $c\neq n$。

分以下几类情况讨论：

1. $c$ 为奇数。此时 $s$ 的奇偶性一定和 $n$ 的奇偶性不同，$s-n$ 必然为奇数。那么，先手可以把一个偶数变成奇数，而不论后手怎么操作，都能保持后手操作完后 $c$ 为奇数且 $c\neq n$。故先手必胜。
2. $c$ 为偶数且 $c\neq n-1$。那么先手不管怎么取，后手的状态都为 1 中描述的先手必胜状态，所以此时后手必胜，先手必败。
3. $c$ 为偶数且 $c=n-1$。如果先手把偶数变为奇数，则还是转化为后手必胜状态。而如果先手把奇数变成偶数，则 $\gcd$ 中就含有因子 $2$，此时需要对那个奇数减一后，除以 $\gcd$（注意不能只除以 $2$）并转换先后手后的情况考虑。

$A$ 中有 $1$ 的情况特殊处理。

由于每次除以 $\gcd$，数的大小都会减少至少一半，所以除的次数是 $O(\log n)$ 的，可以直接做。

Code：

#include<cstdio>
int n,a[100005],cur;
inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
const char*s[]={"First","Second"};
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    for(;;cur^=1){
        int c=0,d=0;
        bool b=0;
        for(int i=1;i<=n;++i)c+=!(a[i]&1),b|=a[i]==1,d=gcd(d,a[i]^(a[i]&1));
        if(b)return puts(s[c&1^!cur]),0;
        if(c&1)return puts(s[cur]),0;
        if(c!=n-1)return puts(s[!cur]),0;
        for(int i=1;i<=n;++i)a[i]/=d;
    }
}