题目传送门
题意简述
筛去所有含有 $7$ 的数 $n$，以及 $n$ 的倍数；并查询 $T$ 次，对于每次查询的数 $x$：如果 $x$ 已被筛去，则输出 -1 ，否则输出离 $x$ 最近的没有被筛去的数。
题目分析
大体分为三步：分离判断是否含 $7$，循环筛去含 $7$ 的数的倍数，查询。
1. 判断一个数是否含 $7$
很简单，这里只贴代码。1
2
3
4
5
6
7
8inline bool fenli(int x){
while(x!=0){
int n=x%10;
if(n==7) return 1;
x/=10;
}
return 0;
}
复杂度很小，近似视为$O(1)$。
2. 按照题意筛去所有含 $7$ 的数的倍数
开一个数组 $f$，类埃氏筛即可。
埃氏筛：一种筛质数的算法，思路是如果一个数 $a$ 是合数，那么 $a$ 的倍数也一定是合数。
1 | for(int i=7;i<=1e7+5;i++){ |
这里有一个坑点，如果输入的数是 $10^7$，会搜到大于 $10^7$ 的数，所以循环应该多循环几次。
3. 关于查询
我们非常开心的写了一份暴力搜索，交上去一看，哇。
为什么呢？如果 $T$ 为$2\times 10^5$，每一个查询的数字为 2699999，循环次数就会被卡到$T\times10^5$次，不T才有鬼呢。
那怎么办呢？
- 二分：查询复杂度$O(Tlogn)$，极限情况下可能会被卡。
- 链表：再定义一个新数组 $nxt$，储存大于等于下标的没有被筛掉的数，查询复杂度 $O(1)$, 肯定没问题。
1
2
3
4for(int i=1e7+1;i>=1;i--){
if(f[i+1]==0) nxt[i]=i+1;
else nxt[i]=nxt[i+1];
}
代码实现
链表，复杂度$O(n\log n+T)$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
using namespace std;
int m,n;
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-48;c=getchar();}
return x*f;
}//快读
inline bool fenli(int x){
while(x!=0){
int n=x%10;
if(n==7) return 1;
x/=10;
}
return 0;
}
bool f[10000010];
int nxt[10000010];
void doit(){//一定要多循环一点
for(int i=7;i<=1e7+5;i++){
if(f[i]==1)continue;
if(i%7==0) f[i]=1;
else if(fenli(i)){
f[i]=1;
for(int j=i;j<=1e7+5;j+=i){
if(f[j]!=1)
f[j]=1;
}
}
else continue;
}
for(int i=1e7+5;i>=1;i--){//倒序维护链表
if(f[i+1]==0) nxt[i]=i+1;
else nxt[i]=nxt[i+1];
}
}
int main(){
cin>>m;
doit();
while(m--){//输出
n=read();
if(f[n]) printf("-1\n");
else {
printf("%d\n",nxt[n]);
}
}
return 0;
}