【AtCoder2305】Decrementing（博弈）

题意

黑板上有n个数，它们的最大公约数为1.于是A和B决定玩一个游戏，两个人轮流进行操作，A先手。
从黑板上的数选择一个不小于2的数，把这个数减去1，然后对于这n个数，除以他们的最大公约数.
当一个人无法操作时便输了。求先手是否必胜。

题解

定义状态1：有奇数个偶数，奇数至少一个
定义状态2：有偶数个偶数，且奇数个数≥2
定义状态3：有偶数个偶数，奇数一个

所有数都为1，为必败态，属于状态2
状态2，无论选哪一个数操作，gcd都不为偶数，操作后，偶数个数-1，只能转移到状态1
而状态1保证可以操作后转为状态2，所以状态2为必败态

状态3，如果选择偶数操作，转换为状态2，必败。选择奇数，继续递归求解。

代码

#include<cstdio> #include<algorithm> using namespace std; const int MAXN=100005; int n,A[MAXN]; bool solve() {
      if(n==1) return false; int cnt[2]={
     0,0}; for(int i=1;i<=n;i++) cnt[A[i]&1]++; if(cnt[0]&1) return true; if((cnt[0]&1)==0&&cnt[1]>=2) return false; int pos=-1; for(int i=1;i<=n&&pos==-1;i++) if(A[i]&1) pos=i; if(A[pos]==1) {
      int sum=0; for(int i=1;i<=n;i++) sum^=(A[i]-1)&1; return sum; } A[pos]--; int g=A[1]; for(int i=2;i<=n;i++) g=__gcd(g,A[i]); for(int i=1;i<=n;i++) A[i]/=g; return solve()^1; } int main() {
      scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&A[i]); if(solve()) puts("First"); else puts("Second"); return 0; }