正题

题目链接:https://www.luogu.com.cn/problem/AT2305

题目大意

$n$个数字两个人进行博弈，每个人的操作为

• 选择一个大于1的数字减一
• 之后所有数字除以所有数字的$gcd$

无法操作者败，保证初始所有数字互质

求是否先手必胜

$1\le n\le 10^5$

解题思路

好妙的题目，先不考虑除$gcd$的话，那么就是考虑${\sum }_{i=1}^n(a_i-1)$的奇偶性。

假设目前为奇状态，那么先手的目的显然是要保持这个奇数状态，注意到如果减去后除以的是一个奇数那么状态显然后手无法改变，所以只要保证序列中有奇数即可，因为如果要有偶数那么就可以减去这个偶数变成奇数先手显然可以保持状态不变。

如果目前为偶状态，那么先手的目前就是要减去后任然是偶状态，那么只有可能除以一个偶数，也就是要让所有的数字都变成偶数。如果奇数个数大于$1$显然不可行，否则减去这个$1$后进行一个子任务的博弈即可。

最多这样$log{a}_i$次所以时间复杂度$O(n{\log }^2{a}_i)$

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,a[N];
int main()
{
	scanf("%d",&n);
	bool k=1,one=0;
	int s=0,z=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		s+=a[i]-1;z+=(a[i]&1);
		one|=(a[i]==1);
	}
	while(1){
		if(s&1)return puts(k?"First":"Second")&0;
		if(one)return puts(k?"Second":"First")&0;
		if(z==1){
			for(int i=1;i<=n;i++)
				if(a[i]&1){a[i]--;break;}
			int d=0;z=one=s=0;
			for(int i=1;i<=n;i++)d=__gcd(a[i],d);
			for(int i=1;i<=n;i++){
				a[i]/=d;s+=a[i]-1;
				z+=(a[i]&1);one|=(a[i]==1);
			}
			k=!k;
		}
		else return puts(k?"Second":"First")&0;
	}
	return 0;
}

最后

以上就是洁净老虎为你收集整理的AT2305-[AGC010D]Decrementing【博弈论】正题的全部内容，希望文章能够帮你解决AT2305-[AGC010D]Decrementing【博弈论】正题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。