[atcoder2305] declining (game)

The question

It's on the blackboard n Number , Their greatest common divisor is 1. therefore A and B Decided to play a game , Two people operate in turn ,A First of all .
Choose one of the numbers on the blackboard that is not less than 2 Number of numbers , Subtract... From this number 1, And then for this n Number , Divided by their greatest common divisor .
When one cannot operate, he loses . If you want to get ahead, you have to win .

Answer key

Define the State 1： There are odd and even numbers , At least one odd number
Define the State 2： There are even numbers , And the number of odd numbers ≥2
Define the State 3： There are even numbers , Odd one

All numbers are 1, It is a state of inevitable failure , Belong to the State 2
state 2, No matter which number operation you choose ,gcd Are not even numbers , After the operation , Even numbers -1, Can only be transferred to state 1
And state 1 Ensure that it can be switched to the state after operation 2, So state 2 It is a state of inevitable failure

state 3, If even operation is selected , Transition to state 2, You will lose . Choose the odd number , Continue to solve recursively .

Code

#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; }