【GZOI2015】石子游戏博弈论 SG函数

题目大意

　　有\(n\)堆石子，两个人可以轮流取石子。每次可以选择一堆石子，做出下列的其中一点操作：

　　1.移去整堆石子

　　2.设石子堆中有\(x\)个石子，取出\(y\)堆石子，其中\(1\leq y<x\)且\((x,y)=1\)

　　取出最后一颗石子的人胜利。问先手胜还是后手胜。

　　\(n\leq 100\)，每堆石子个数\(a_i\leq {10}^6\)

题解

　　基础知识：SG函数。

　　令\(x\)为某堆石子的个数。

　　\(SG(i)=mex(SG(j)~~~~((i,j)=1)\)

　　先用暴力求一遍SG值，然后会发现：

　　当\(x\)为质数时，\(SG(x)=\)\(x\)是第几个质数\(+1\)。因为前面的质数都可以选，所以就是这个。

　　当\(x\)不是质数时，设\(y\)为\(x\)的最小质因子，则\(SG(x)=SG(y)\)。因为\(y\)之前的都可以选，\(y\)不能选，所以就是\(SG(y)\)。

　　然后直接线性筛计算答案。

　　时间复杂度：\(O(a+n)\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

#include<cmath>

#include<functional>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

void sort(int &a,int &b)

{

	if(a>b)

		swap(a,b);

}

void open(const char *s)

{

#ifndef ONLINE_JUDGE

	char str[100];

	sprintf(str,"%s.in",s);

	freopen(str,"r",stdin);

	sprintf(str,"%s.out",s);

	freopen(str,"w",stdout);

#endif

}

int rd()

{

	int s=0,c;

	while((c=getchar())<'0'||c>'9');

	do

	{

		s=s*10+c-'0';

	}

	while((c=getchar())>='0'&&c<='9');

	return s;

}

int upmin(int &a,int b)

{

	if(b<a)

	{

		a=b;

		return 1;

	}

	return 0;

}

int upmax(int &a,int b)

{

	if(b>a)

	{

		a=b;

		return 1;

	}

	return 0;

}

int gcd(int a,int b)

{

	return b?gcd(b,a%b):a;

}

int sg[1000010];

int pri[100010];

int cnt;

int main()

{

	sg[0]=0;

	sg[1]=1;

	int i,j;

	for(i=2;i<=1000000;i++)

	{

		if(!sg[i])

		{

			pri[++cnt]=i;

			sg[i]=cnt+1;

		}

		for(j=1;j<=cnt&&i*pri[j]<=1000000;j++)

		{

			sg[i*pri[j]]=sg[pri[j]];

			if(i%pri[j]==0)

				break;

		}

	}

	int t;

	scanf("%d",&t);

	while(t--)

	{

		int n,x,s=0;

		scanf("%d",&n);

		for(i=1;i<=n;i++)

		{

			scanf("%d",&x);

			s^=sg[x];

		}

		if(s)

			printf("Alice\n");

		else

			printf("Bob\n");

	}

	return 0;

}

巴特西

【GZOI2015】石子游戏博弈论 SG函数

题目大意

题解

代码

最新文章

热门文章

巴特西

【GZOI2015】石子游戏 博弈论 SG函数

题目大意

题解

代码

最新文章

热门文章

【GZOI2015】石子游戏博弈论 SG函数