Atcoder Grand Contest 010 D Decrementing

98 阅读 0 评论 65 点赞

我是靠谱客的博主欣喜荔枝，最近开发中收集的这篇文章主要介绍Atcoder Grand Contest 010 D Decrementing，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Decrementing

Problem Statement

给出 $n$ 个数，两个人玩游戏，每一次可以选择一个数将其减 $1$ ，然后所有数除以全部数的 $gcd$ ，减到 $1$ 后不能再减，问是先手必胜还是后手必胜。
保证一开始所有数的 $gcd$ =1。

Data Constraint

$1≦n≦10^5$
$1≦A_i ≦10^9$

Solution

考虑在什么情况下可以获胜，那一定是序列形如k,k,k,k,…,k+1,k,k,k..k这样的序列可以一步获胜。
因此一个人一定不会让对手获得这样的状态，但只有获得这样的状态才会赢，因而获胜的那个人一定是拿到了形如1,1,1,1,….2,1,1,1…..1这样的序列。

接下来给出结论，若原序列中有奇数个偶数，先手必胜。
先手先操作可以保证序列中同时存在偶数和奇数，这样即使除去 $gcd$ 后每个数的奇偶性都不会变，于是每两轮操作原序列始终是有奇数个偶数，所以先手最后一定会拿到上述的必胜序列（只有一个2和若干个1）。

倘若原序列中有偶数个偶数，那先手会尽量不让对方获得“奇数个偶数”的状态，那什么情况下后手一定会拿到“奇数个偶数”的必胜状态呢？那就是原序列中有至少2个奇数或原序列中存在1，这种情况下后手一定会拿到“奇数个偶数”的必胜状态。

剩下的一种情况就是原序列中只有一个奇数且这个奇数不为1。
因为减其他的数都是必败状态，因而只好减那个奇数，这样整个序列就都是偶数了，全部除以 $gcd$ ，便成了另一个子问题。

由于全部都是偶数，所以每次至少除以2，所以时间复杂度为 $O(n log max(Ai))$

Code

#include<bits/stdc++.h>
#define fo(i,j,l) for(int i=j;i<=l;++i)
#define fd(i,j,l) for(int i=j;i>=l;--i)

using namespace std;
typedef long long ll;
const ll N=1e5+7;

int a[N],n;

inline int read()
{
    int o=0; char ch=' ';
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';ch=getchar())o=o*10+ch-48;
    return o;
}

inline int gcd(int x,int y)
{return y==0?x:gcd(y,x%y);} 

int solve()
{
    int odd=0,even=0,k;
    fo(i,1,n)(a[i]&1)?++odd:++even;
    if(even&1)return 1;
    if(odd>1)return 0;
    fo(i,1,n)if(a[i]&1){k=i;break;}
    if(a[k]==1)return 0;
    --a[k];
    int g=a[1];
    fo(i,2,n){
        g=gcd(g,a[i]);
        if(g==1)break;
    }
    fo(i,1,n)a[i]=a[i]/g;
    return (1^solve());
}

int main()
{
    n=read();
    fo(i,1,n)a[i]=read();
    if(solve()==1)puts("First");else puts("Second");
}