[agc010d]Decrementing

题目大意

有一个序列a[]，两个绝顶聪明的人在操作它，每次操作，选一个大于1的数，让它-1，然后再让整个序列每个元素除以所有数的GCD。不能操作的输。保证一开始GCD=1，问先手还是后手必胜。
n<=1e5,a[i]<=1e9

解题思路

看上去是一道结论博弈题。但是似乎有点复杂。
考虑一种简单的情况，要是有个1，那么无论怎样GCD都=1，那么这时候只需要统计sum{a[i]-1}就知道谁必胜了。
考虑如果-1之后要除gcd了，那么如果操作前sum是奇数，先手肯定不想让d是偶数，因为奇偶性有可能改变，万一之后gcd都是1，就输了。可以发现的是，这种情况下，d可以保证不为偶数，因为一开始的GCD=1保证序列至少有一个奇数，那么先手只要操作另外一个偶数，那么GCD不可能为偶数。也就是说，如果有奇数个偶数，先手必胜。
那么其他情况就后手必胜？也不一定，假如只有一个奇数，先手操作他，有可能让sum奇偶性改变，这种情况递归着做即可。
其他情况怎样先手都陷入被动，后手必胜。
注意特判奇数是1。

代码

#include<cstdio> 
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define fo(i,j,k) for(i=j;i<=k;i++)
#define fd(i,j,k) for(i=j;i>=k;i--)
#define cmax(a,b) (a=(a>b)?a:b)
#define cmin(a,b) (a=(a<b)?a:b)
typedef long long ll;
const int N=1e6+5,M=2e6+5,mo=1e9+7;
int a[N],d,x,i,n,pp;
int gcd(int a,int b)
{
    if (!b) return a;
    return gcd(b,a%b);
}
int dfs()
{
    x=0;
    pp=0;
    fo(i,1,n) if (a[i]%2==0) x++;
    else 
    {
        if (a[i]==1) pp=1;
        a[i]--;
    }
    if (x%2) return 0;
    if (x==n-1&&!pp)
    {
        d=a[1];
        fo(i,2,n) d=gcd(d,a[i]);
        fo(i,1,n) a[i]/=d;
        return dfs()^1;
    }
    return 1;
}
int main()
{
    freopen("t10.in","r",stdin);
    freopen("t10.out","w",stdout);
    scanf("%d",&n);
    fo(i,1,n) 
        scanf("%d",a+i);
    if (dfs()==0) printf("First");else
    printf("Second");
}

最后

以上就是自然太阳为你收集整理的[agc010d]Decrementing的全部内容，希望文章能够帮你解决[agc010d]Decrementing所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。