【每日一题】1月22日题目精讲

题号 NC21350
名称 质数与合数

戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

一个模拟题,得在自己清醒的时候打...不然就会乱坟岗..
思路很简单,就是找到两个质数是不是差>(k+1),因为我们都足够聪明.那么,你下次肯定会取1(假设我是FFF),而我取k都到不了,那么我必输.其它肯定是我必胜,因为1,2,3你都不能取.所以这题就没了.但是,细节是真的多...具体看代码吧...码风还行..

#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)
        {
            flag=false;
        }
    }
   // cout<<prime[m]<<endl;
    if(n-prime[m]>k) {puts("0");return 0;}
    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;
            ans++;
            if(prime[xb]<=3) break;
            n=prime[xb]-1;
            ans++;
        }
        printf("%d\n",ans);
    }
    else//GGG可以赢
    {
       // cout<<prime[pos]<<endl;
        int wz,ans=0;int cnt=m;
        if(n==prime[m])
        {
            if(n-k<=prime[m-1]) cnt--;
            else                {puts("0");return 0;}
        }
        while(1)
        {
            if(n-k<=prime[cnt])
            {
                n=prime[cnt];
            }
            else break;
            ans++;
            int xb=upper_bound(prime,prime+m,n-k)-prime;
            n=prime[xb]-1;
            cnt=xb-1;
            ans++;
        }
        if(ans) printf("%d\n",-ans);
        else    puts("0");
    }
    return 0;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目1月29日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴