看,这是我写的60分代码。
#include <bits/stdc++.h>
using namespace std;
#define int long long//我可能比较喜欢无脑开long long
#define N 10001000
int T, x, las;
int f[N],nex[N];
bool check(int x){
while (x!=0){
if (x % 10 == 7) return 1;
x /= 10;
}
return 0;
}//检查该数是否含有7
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
for (int i = 1; i <= N; i++){
if (f[i]) continue;
if (check(i)){
for (int j = 1; j <= N / i; j++) f[j*i] = 1;
continue;
}
nex[las] = i;
las = i;
}//筛法
cin>>T;
while (T--){
cin>>x;
if(f[x]==1) cout<<"-1\n";
else cout<<nex[x]<<"\n";
}//O(1)查表
return 0;
}
后来我看来看去找不出错误,就去看了题解,找到了问题所在。
AC:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 10001000
int T, x, las;
int f[N],nex[N];
bool check(int x){
while (x!=0){
if (x % 10 == 7) return 1;
x /= 10;
}
return 0;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
for (int i = 1; i <= N - 10; i++){
if (f[i]) continue;
if (check(i)){
for (int j = 1; j <= (N-10) / i; j++) f[j*i] = 1;
continue;
}
nex[las] = i;
las = i;
}
cin>>T;
while (T--){
cin>>x;
if(f[x]==1) cout<<"-1\n";
else cout<<nex[x]<<"\n";
}
return 0;
}
代码不同出在于筛法部分
60:
for (int i = 1; i <= N; i++){
if (f[i]) continue;
if (check(i)){
for (int j = 1; j <= N / i; j++) f[j*i] = 1;
continue;
}
nex[las] = i;
las = i;
}
100:
for (int i = 1; i <= N - 10; i++){
if (f[i]) continue;
if (check(i)){
for (int j = 1; j <= (N-10) / i; j++) f[j*i] = 1;
continue;
}
nex[las] = i;
las = i;
}
为什么筛法只需筛到N-10,而不是N?
hack又是什么?