题目描述
有n个整数,其中第i个数为Ai。这些数字的gcd为1。两人轮流操作,每次操作把一个大于1的数减1,并把所有数除以所有数的最大公约数,最后无法操作者输,求是否先手必胜。
如果当前的sum为偶数,那么减一之后sum变为奇数,gcd必为奇数,而任意数除一个奇数后奇偶性不变,故这步走完后sum必然为奇数。
如果当前的sum为奇数,减一之后sum变为偶数,如果当前全为偶数,那么除完gcd后奇偶不一定,否则sum依然为偶数。
当局面全为1的时候先手必败,此时的奇偶为$n%2$,考虑先手怎样控制局面取得胜利。
假设先手的局面$sum\%2!=n\%2$,那么先手一定必胜,后手改变局面的唯一机会是使减完后gcd为2的倍数,则n个数都%2后必须只有一个1,先手只要每回把一个0变成1后手就无法翻盘。
那如果$sum\%2=n\%2$,如果满足n个数%2后只有一个1且先手必须要把1变0先手才可能赢,否则必败。
模拟一下过程,gcd为2的倍数的次数最多log次。
1 #include2 #define ll long long 3 using namespace std; 4 int n; 5 int a[100005]; 6 ll sum=0; 7 void print(int x) 8 { 9 if(!x)puts("First");10 else puts("Second");11 }12 int gcd(int x,int y)13 {14 if(!y)return x;15 return gcd(y,x%y);16 }17 int main()18 {19 scanf("%d",&n);20 for(int i=1;i<=n;i++)21 {22 scanf("%d",&a[i]);sum+=a[i];23 }24 int now=0;25 while(1)26 {27 if(n%2!=sum%2)return print(now),0;28 int id=0;29 for(int i=1;i<=n;i++)30 {31 if(a[i]%2==1&&a[i]!=1)32 {33 if(!id)id=i;34 else return print(now^1),0;35 }36 }37 if(!id)return print(now^1),0;38 a[id]--;39 int g=a[1];for(int i=2;i<=n;i++)g=gcd(g,a[i]);40 sum=0;41 for(int i=1;i<=n;i++)a[i]/=g,sum+=a[i];42 now^=1;43 }44 return 0;45 }