DD 和 MM 正在玩取石子游戏。他们的游戏规则是这样的：桌上有若干石子，DD 先取，轮流取，每次必须取质数个。如果某一时刻某一方无法从桌上的石子中取质数个，比如说剩下 0 个或 1 个石子，那么他/她就输了。
DD 和 MM 都很聪明，不管哪方存在一个可以必胜的最优策略，他/她都会按照最优策略保证胜利。于是，DD 想知道，对于给定的桌面上的石子数，他究竟能不能取得胜利呢？
当 DD 确定会取得胜利时，他会说：“不管 MM 选择怎样的取石子策略，我都能保证至多 X 步以后就能取得胜利。”那么，最小的满足要求的 X 是多少呢？注意，不管是 DD 取一次石子还是 MM 取一次石子都应该被计算为“一步”。
首先翻译题意：每个人轮流取石子，只能取质数个，哪一方不能取，则视为这一方输。
显而易见这道题是有一个博弈的背景的，那么根据博弈的那两个经典结论，只要能转移到一个必败态的就是必胜态，如果一个必败态都转移不到的就是比败态。
那么我们首先将0与1初始化为必败态，对于每一个数i，减去所有比i小的所有质数，如果有必败态即为必胜态，如果都转移不到就是必败态了。
接着再留心一下题目，题目要求至多x步，那么就是取得胜利的最多次数了。这样的话因为已经求出了哪个点是必胜态与必败态，我们也便可以推出转移方程：
如果这个状态i是必胜态，那么能转移到它的一定是比它小的j的必败态，因为知道自己会胜利，那么一定会选择其中的最小步数。
如果这个状态i是必败态，那么能转移到它的就是比它小的任意一个数了，因为知道自己会失败，那么一定会选择其中的最大步数。
这道题目最恶心的就是卡常数了。于此我使用了o(n)的素数筛来筛出质数，并同时处理出比i小的最大素数是第几个素数，这样能够尽量减少后期的枚举量，以便不被卡常。
下附AC代码。
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #define maxn 20005 using namespace std; int cnt=0; int prime[maxn]; int jud[maxn]; int pos[maxn]; void getprime() { for (int i=2;i<maxn;i++) { if (!jud[i]) prime[++cnt]=i; for (int j=1; j<=cnt && prime[j]*i<maxn;j++) { jud[i*prime[j]]=1; if (i%prime[j]==0) break; } pos[i]=cnt; } } int vis[maxn]; int step[maxn]; int main() { getprime(); for(int i=2;i<=20000;i++) for(int j=pos[i];j>=1;j--) if(vis[i-prime[j]]==0) { vis[i]=1; break; } for(int i=2;i<=20000;i++) { if(vis[i]) { int minn=30000; for(int j=pos[i];j>=1;j--) { if(vis[i-prime[j]]==0 && step[i-prime[j]]<minn) { minn=step[i-prime[j]]; } } step[i]=minn+1; } else { int maxx=-30000; for(int j=pos[i];j>=1;j--) { if(step[i-prime[j]]>maxx) { maxx=step[i-prime[j]]; } } step[i]=maxx+1; } } int q; cin>>q; while(q--) { int x; cin>>x; if(vis[x]==0) { cout<<"-1"<<endl; } else { cout<<step[x]<<endl; } } }
