agc010D Decrementing

题目

题解

获胜条件

显然当局面为k,k,kk+1k,k,k\cdots k+1的时候,先手必胜。

但是除了k=1的时候,或者开局的时候,对手都可以阻止这个局面。

那么获胜条件显然是拿到1,1,1,121,1,1,1\cdots 2的时候,此时有1个(奇数个)偶数。

显而易见,如果gcd为奇数的时候,所有数除以gcd后奇偶性不变。

分类讨论:

包含1

略。

####奇数个偶数

如果有奇数个偶数,由于gcd=1,显然至少有一个奇数。

把其中一个偶数-1变成奇数,那么对手手里至少有2个奇数,显然不可能一步使得gcd为偶数。

那么对手怎么拿,偶数个数都会变回奇数。

不断这么操作,那么先手必胜。

偶数个奇数 且奇数个数>1

发现你不管怎么操作都会使对手有奇数个偶数,则先手必败。

偶数个奇数,且奇数个数为1

奇数为1的情况讨论过了。

发现你如果把偶数-1,对面就必胜了。

你只能把奇数-1,然后要全部除以一个偶数,并轮到对手。递归计算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/*
Author: CNYALI_LK
LANG: C++
PROG: d.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
int s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
int a[102424],n;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int solve(){
int xs=1,zs;
while(1){
zs=0;
for(int i=1;i<=n;++i)if(a[i]==1)zs=1;
if(zs){
for(int i=1;i<=n;++i)xs=xs^((a[i]-1)&1);
return !xs;
}
for(int i=1;i<=n;++i)if(!(a[i]&1))++zs;
if(zs&1)return xs;
else if(n-zs>1)return !xs;
int g=0;
for(int i=1;i<=n;++i){
if(a[i]&1)--a[i];
g=gcd(g,a[i]);
}
for(int i=1;i<=n;++i)a[i]/=g;
xs^=1;
}
}
int main(){
#ifdef cnyali_lk
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
#endif
n=read();
for(int i=1;i<=n;++i)a[i]=read();
printf(solve()?"First\n":"Second\n");
return 0;
}
文章目录
  1. 1. 题解
    1. 1.1. 获胜条件
    2. 1.2. 包含1
    3. 1.3. 偶数个奇数 且奇数个数>1
    4. 1.4. 偶数个奇数,且奇数个数为1
|

博客使用Disqus作为评论系统