记录编号	164063	评测结果	AAAAAAAAAA
题目名称	56.质数取石子	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	1.722 s
提交时间	2015-05-27 21:34:17	内存使用	0.77 MiB

#include<cstdio>
#include<string.h>
#include<iostream>
using namespace std;
int maxn=0x7fffffff,T,SG[20010],f[30010],p[30010]={0},tot=0,H[20010],b[20010];
void getprime(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(p[i]==0) f[++tot]=i;
		for(int k=1;k<=tot;k++)
		{
			if(i*f[k]>n) break;
			p[i*f[k]]=1;
			if(i%f[k]==0) break;
		}
	}
}
void getSG(int r)
{
	SG[0]=0;
	SG[1]=0;
	b[0]=b[1]=0;
	for(int i=2;i<=r;i++)
	{
		memset(H,0,sizeof(H));
		int mi=0;
		b[i]=maxn;
		for(int j=1;f[j]<=i;j++)
		{
			H[SG[i-f[j]]]=1;
			if(SG[i-f[j]]==0)
				b[i]=min(b[i],b[i-f[j]]+1);
			mi=max(mi,b[i-f[j]]+1);
		}
		for(int j=0;j<=i;j++)
		{
			if(H[j]==0)
			{
				SG[i]=j;
				break;
			}
		}
		if(SG[i]==0) b[i]=mi;
		//cout<<i<<" "<<SG[i]<<endl;
	}
}
int main()
{
	freopen("stonegame.in","r",stdin);
	freopen("stonegame.out","w",stdout);
	scanf("%d",&T);
	getprime(30000);
	getSG(20000);
	int a;
	for(int i=1;i<=T;i++)
	{
		scanf("%d",&a);
		if(SG[a]==0) printf("-1\n");
		else printf("%d\n",b[a]);
	}
	return 0;
}