筛法求助
查看原帖
筛法求助
1258210
pipilong2024楼主2024/12/5 12:41

看,这是我写的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又是什么?

2024/12/5 12:41
加载中...