AGC010D Decrementing

传送门

题意：
两人发现了一块黑板.现在黑板上有n个数,两人惊奇地发现它们的最大公约数为1.于是他们决定玩一个游戏,两个人轮流进行操作,Hellen先手.
从黑板上的数选择一个不小于2的数,把这个数减去1.然后对于这n个数,除以他们的最大公约数.
当一个人无法操作时便输了.他们都很聪明,每次都会进行最优的操作,问最后哪一个人能够获胜.

题解：
考试时没想到分类讨论，结果大暴力还写丑了…哭唧唧。
看了题解瞬间感觉自己好蠢系列
n=1时先手必败（原因：gcd为1，这个数只能为1）。
显然不可能全是偶数。
情形1：奇数个偶数，至少1个奇数。
情形2：偶数个偶数，至少2个奇数。
情形3：偶数个偶数，1个奇数。
显然，全1属于情形2，为必败态。
情形1选择某个偶数可以转移到情形2，情形2只能转移到情形1.所以（？）情形2为先手必败，情形1为先手必胜。
至于情形3，选择偶数后会转移到情形1导致必败，那么就只能选择奇数，然后递归。
最后我加了一个判断：如果其中有一个1，那么如果(a₁-1)+…+(a_n-1)为奇数，就是先手胜，否则后手胜。

代码：

#include<cstdio>
#define maxn 100005
#define LL long long
using namespace std;
int n,a[maxn];
int gcd(int a,int b)
{
	if(!b) return a;
	return gcd(b,a%b);
}
bool dfs(int a[])
{
	if(n==1) return false;
	int cnte=0,cnto=0,poso=-1;
	for(int i=1;i<=n;i++)
		if(a[i]%2) cnto++,poso=i;
		else cnte++;
	if(cnte%2) return true;
	else if(cnto>1) return false;
	else
	{
		if(a[poso]==1)
		{
			LL tmp=0;
			for(int i=1;i<=n;i++) tmp+=1ll*(a[i]-1);
			return tmp%2;
		}
		a[poso]--;
		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 dfs(a)^1;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	printf("%sn",dfs(a)?"First":"Second");
}

最后

以上就是自由篮球为你收集整理的AGC010D Decrementing的全部内容，希望文章能够帮你解决AGC010D Decrementing所遇到的程序开发问题。

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