简要题意
小Z在玩报数游戏，这个游戏有一个规则，就是对于一个正整数 \(x\)，如果满足 \(7 \mid x\) 或 \(x\) 的十进制写法中含有 \(7\) 或是十进制写法含有 \(7\) 的倍数，那么这个数就得跳过。
有 \(T(1 \leq T \leq 2 \times 10^{5})\) 组数据，每组数据给出一个 \(x\)，如果这个数应该跳过，输出 \(-1\)，否则输出比 \(x(1 \leq x \leq 10^{7})\) 大且不会被跳过的数中最小的。
思路
NOIP2021送分题。
看到如此恐怖的数据，想到筛法。我们可以用一个类似埃氏筛的方法，筛出所有数。然后直接判断。
但是求下一个数呢？如果一个一个找就很憨了（不信？试一试 \(x=7 \times 10^{6} - 1\)）我们可以在筛法时用一个类似链表的方法预处理。
时间复杂度 \(O(\max\{x\}\log\max\{x\}+T)\)，完全可以过。
代码
坑点：
- 十年OI一场空，不开
long long见祖宗。 - 筛法界需要比 \(10^7\) 大一点，如 \(10^7+1\)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int vis[10000005];
int nxt[10000005];
bool isseven(int x){
while(x){
if(x%10==7)return 1;
x/=10;
}
return 0;
}
signed main(){
int pre=0;
for(int i=1;i<=10000001;i++){
if(vis[i]){continue;} // 剪枝
if(isseven(i)){
for(int j=1;i*j<=10000001;j++){
vis[i*j]=1;
}
}
else{
nxt[pre]=i;
pre=i;
}
}
int t;
cin>>t;
while(t--){
int x;
cin>>x;
cout<<(vis[x]?-1:nxt[x])<<'\n';
}
return 0;
}