Codeforces Round #948 (Div. 2) B （素数筛+思维）

题目链接： http://codeforces.com/contest/948/problem/B

2018-03-15 17:55:53

题意：小花和她的好朋友嘉瑜君玩游戏第一个数字Xo确定后面的数字X1由前面一个数字确定确定的方式是找到小于等于Xo的一个质数在质数的倍数中不小于Xo的最小的数字就是下一个数字 NODE：由上文可知当Xo为质数的时候 Xo与X1可能相等给出一个X2 要求求出最小的Xo

思路：先求出X1 刚开始的想法是这道题是否存在最优子结构每一步都要求最小的话是不是到Xo也就最小了看过样例之后就会发现不是的样例输入的是14 那么X1最小可以取8 比8小的质数取7 7的倍数中比8大的最小的就是14 X1等于8 那么Xo最小可以取7 比7小的质数取2 那么Xo最小也就是7了但是这样是不对的因为当X1不去最小取10时 Xo可以取到6 所以我的想法就是吧所有的X1的取值求出来再把Xo所有的取值取出来再求最小就好了由题意可知质数比第一个数字小质数的倍数刚好大于是第二个数字第二个数字刚好大于第一个数字也就是连个数中间不存在质数的其他倍数假设第二个数字是质数的x倍（x>=2）那么第一个数字就是大于质数的x-1倍小于等于x倍的数字由此可以根据X2把所有的X1求出来进而求出所有的X0

错因：因为写的不够优雅所以超时了因为符合要求的X1与X2之间差的就是一个质数大小的范围所以只要找到能被X2整除的最大的那个质数就好了同理Xo 超时的原因可能在于我每次都算一边可以把这个初始化出来每次直接调用

代码如下：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>

using namespace std;

#define Max 1000000

int n;
int prim[1000005];///为0的代表是素数 不为零的代表的是能整除的最大的素数是多少 时间复杂度接近nlogn

void Isprim()
{
    memset(prim , 0 , sizeof(prim));
    prim[1] = 1;///这个题中用不到1 设置一个不为0的数即可
    ///一个质数的不大于他本身的质数就是他自己
    for(int i=2; i<=1000000; i++)
    {
        if( prim[i]==0 )
        {
            for(int j=i*2; j<=1000000; j+=i)
            {
                prim[j] = i;
            }
        }
    }
}

void debug()
{
    for(int i=1; i<=100; i++)
    {
        printf("%d...
" , prim[i]);
    }
}

int main()
{
    Isprim();
//    debug();
    while( scanf("%d" , &n) != EOF )
    {
        int minn = 1e9;
        if( prim[n]==0 )
        {
            minn = n;
        }
        else
        {
            for(int i=n-prim[n]+1; i<=n; i++)//X1 可以是这些数字
            {
                if( prim[i]==0 )
                {
                    minn = min(minn , i);
                }
                else
                {
                    minn = min(minn , i-prim[i]+1);
                }
            }
        }
        printf("%d
" , minn);
    }

    return 0;
}