【题目描述】

【输入】

【输出】

【输入样例】

4
6
33
69
300

【输出样例】

8
36
80
‐1

这个问题应该是几个题里面唯一一个能让普及组的也做一下的问题。

题目就是说你写一个sv函数初始化一下记录表，然后在表里查询一下输出答案。这个基本就是素数筛的情况，只是判定的时候有所不同：

bool Sv(int k){while(k){if(k%10==7)return true;k/=10;}return false;
}

void Init(){for(int i=1;i<=MXX;i++){if(!table[i]&&Sv(i)){for(int j=1;i*j<=MXX;j++){table[i*j]=true;}}}
}

函数的意思就是对没检测过的进行检测，形式和素数筛一样，但MXX是不能开根号的，因为它不是一个简单的乘法，无法正确处理100007（随便打的，假定它是个素数）这样的情况。其中table即是结果，又起到了加速作用：

#include<iostream>
#include<cmath>
using namespace std;
//把每个数的情况放到桶里
const int MXX=1e7+11;
bool table[MXX];bool Sv(int k){while(k){if(k%10==7)return true;k/=10;}return false;
}void Init(){for(int i=1;i<=MXX;i++){if(!table[i]&&Sv(i)){for(int j=1;i*j<=MXX;j++){table[i*j]=true;}}}
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t,x;Init();cin>>t;while(t--){cin>>x;if(table[x]){cout<<"-1\n";}else{x++;while(table[x]){	//这个查找是浪费大量时间的x++;}cout<<x<<"\n";}}return 0;	
}

这样的代码10个测试点可以过7个，另外7个是超时的。代码里已经注释出来了，查询太浪费时间了：题目实际上给了非常明确的提示，自己想一想，7，14，17，21，27……70-79，87……当数位变多之后，连续的带7的长度会很长。

怎么能简化这个每次都循环查找东西呢？标志表我们已经有了，只需要稍微改一下：标志表里记录的是当前这个数的情况，改为指向下一个不是7相关数的情况，这样只需要在此预处理数据，增加一次循环，以后都能直接读了：

#include<iostream>
#include<cmath>
using namespace std;const int MXX=1e7+11;
int table[MXX];bool Sv(int k){while(k){if(k%10==7)return true;k/=10;}return false;
}void Init(){for(int i=1;i<=MXX;i++){if(!table[i]&&Sv(i)){for(int j=1;i*j<=MXX;j++){table[i*j]=true;}}}//变成记录下一个不是7相关的数是几int last=1;for(int i=2;i<=MXX;i++){if(!table[i]){table[last]=i;last=i;}else{table[i]=i;}}
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t,x;Init();cin>>t;while(t--){cin>>x;if(table[x]==x){cout<<"-1\n";}else{cout<<table[x]<<"\n";}}return 0;
}

细节：

10000000后面第一个非7相关的数是10000010