题解 AT2305 【Decrementing】

Ebola · 2018-09-11 19:43:50 · 题解

这题的难点，是你要发现若干个偶数的gcd居然可能大于2！这个超级难的！

好吧言归正传。。。

结论一：如果一开始有一个1，其它都是偶数，那么若是奇数个偶数，先手必胜，否则后手必胜（显然）

结论二：如果一开始有奇数个偶数，先手必胜。

说明：如果先手能保证每人每次只能取一个，那么他就赢了。要想保证每人每次只能取一个也很简单，先手只需任选一个偶数减1，再算上初始局面必然包含的一个奇数（否则初始gcd不为1），这样就至少有两个奇数了。此时若序列长度大于2，那么序列的gcd必然为1，并且再让任意一个数减1，序列的gcd仍然为1，后手此时显然非常鸡肋。

特殊情况是序列长度为2，那先手减了1之后，可能两数相等，那正好直接赢了；要是不相等，并且减1之后出现了倍数关系，那没什么影响，显然一个是另一个的奇数倍，约去gcd后就是一个1加上一个奇数，此时显然先手就赢了。

结论三：如果一开始有大于一个奇数，以及偶数个偶数，后手必胜

说明：因为有大于一个奇数，所以选任意一个数减一，gcd必然还为1，此时结论二中的情况就轮到了后手的手上，先手就只能咕咕咕了

其他情况下（一开始有偶数个偶数以及一个奇数），让那个奇数减1，然后序列整体除以gcd（对，是gcd，不是2，艹），再重复进行上述三种判断。因为每次至少除2，所以递归层数是log级别的

#include<bits/stdc++.h>
using namespace std;

const int N=100010;
int a[N],n,cnt[2];

bool gao()
{
    for(int i=1;i<=n;i++)
        if(a[i]&1) a[i]--;
    cnt[0]=cnt[1]=0;
    int gcd=a[1];
    for(int i=2;i<=n;i++)
        gcd=__gcd(a[i],gcd);
    for(int i=1;i<=n;i++)
        cnt[(a[i]/=gcd)&1]++;
    if(cnt[0]&1) return 1;
    else if(cnt[1]>1) return 0;
    else
    {
        for(int i=1;i<=n;i++)
            if(a[i]==1) return cnt[0]&1?1:0;
        return gao()^1;
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        cnt[a[i]&1]++;
    }
    if(cnt[0]&1) puts("First");
    else if(cnt[1]>1) puts("Second");
    else
    {
        for(int i=1;i<=n;i++)
            if(a[i]==1){puts(cnt[0]&1?"First":"Second");return 0;}
        puts(gao()^1?"First":"Second");
    }
    return 0;
}