质数与合数

题意：

FFF和GGG正在玩一个质数与合数的游戏
一开始有N个石头
FFF和GGG轮流对这堆石头进行操作，FFF每次选择1到K之间的一个数x，并拿走x个石头，拿走之后剩下的石头数量必须是质数
接着GGG进行同样的操作，但是要求拿走之后剩下的石头数量必须是合数
假设双方都足够聪明，第一个不能操作的人输
以为到这里就结束了？
显然，一开始两人之间有一人知道自己有必胜策略，现在他想要尽可能快的赢，另外一个人则想要尽可能输的慢一点
给你N与K，假设游戏最终持续了X轮，如果FFF赢了，输出X，否则输出-X
注意：1既不是质数也不是合数

题解：

判断输赢很简单，因为每次取数范围是[1,K]，而FFF要每次取完都是质数，如果存在两个相邻的质数，差大于K+1，也就是无论取任何数都不可能剩下为质数，那么FFF就输了，反之FFF必胜，因为FFF都能取到，但是游戏到最后时，剩下34,5，GGG都会输,所以FFF必胜
本题麻烦在计算游戏会进行几轮
根据题意，游戏的胜负从一开始就给定了，但是赢的人想赶紧赢，输的人想慢点输。如果是FFF输了，保证GGG步骤最少，呢么GGG每次都走到下一个素数的前一个的位置，（相当于故意恶心FFF，让FFF正好错过自己的质数），FFF就永远不能跳过相差大于k+1的两个点。
就比如当前点是31，K=3，轮到GGG了，现在离30最近的质数是29，GGG就走到28（因为GGG不能走到质数），让FFF错过自己的质数
如果是FFF赢了，他想赶紧结束比赛就会尽可能跳更远的质数，而GGG为了拖慢，每次只会跳一个单位，当然当跳到2,3时GGG就算输了，不能再跳

代码：

懒得写了，官方代码，但是我每句话做了详细注释

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+5;

int prime[N],cnt=0;
bool st[N];

void init()
{
    for(int i=2;i<=N-5;i++)
    {
        if(!st[i]) {prime[cnt++]=i;}
        for(int j=0;prime[j]<=(N-5)/i;j++)
        {
            st[i*prime[j]]=true;
            if(i%prime[j]==0)
            {
                break;
            }
        }
    }
}

int main()
{
    init();
    bool flag=true;
    int n,k,pos,m=0;
    scanf("%d%d",&n,&k);
    if(n<=2) {puts("0");return 0;}
    for(int i=1;prime[i]<=n;i++)
    {
        m++;
        if(prime[i]-prime[i-1]>k+1)//如果有距离大于k+1，FFF就输了 
        {
            flag=false;
        }
    }
    if(n-prime[m]>k) {puts("0");return 0;}//如果第一步FFF都跳不了 
    if(flag)//FFF可以赢
    {
       // puts("9");
        //FFF可以赢,那么每次选k的时候会尽量多选些质数.
        int wz,ans=0;
        while(1)
        {
            wz=n-k;
            int xb=lower_bound(prime,prime+m,wz)-prime;
            //找第一个大于等于wz的质数，也就是离n最远的质数 
            ans++;//FFF操作完毕 
            if(prime[xb]<=3) break;//如果当前点小于等于3，GGG就输掉比赛 
            n=prime[xb]-1;//GGG所跳点 
            ans++;//GGG操作完毕 
        }
        printf("%d\n",ans);
    }
    else//GGG可以赢
    {
       // cout<<prime[pos]<<endl;
        int wz,ans=0;int cnt=m;
        if(n==prime[m])//如果起点就是质数 
        {
            if(n<=prime[m-1]+k) cnt--;//如果第一步FFF可以走的话 
            else 
            {
                puts("0");
                return 0;
            }
        }
        while(1)
        {
            if(n<=prime[cnt]+k)//如果FFF可以走 
            {
                n=prime[cnt];//FFF走一步 
            }
            else break;
            ans++;
            int wz=n-k; 
            int xb=upper_bound(prime,prime+m,wz)-prime;
            //找第一个大于n-k的质数，也就是离n最近的质数 
            n=prime[xb]-1;//GG正好走到prime[xb]-1(也就是素数的前一个位置来恶心FFF) 
            cnt=xb-1;//FFF下一个最近的质数是第xb-1位（因为xb位被GGG给“完美错过”） 
            ans++;
        }
        if(ans) printf("%d\n",-ans);
        else    puts("0");
    }
    return 0;
}