RE求调

AC_bee @ 2024-10-04 12:19:13

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e7;
long long n,z[MAXN],p[MAXN],m,q;
long long u[MAXN],t;
int main(){
    scanf("%lld%lld",&n,&t);
    for(long long q=2;q<=n;q++){
        if(z[q]==0) {
            z[q]=q;
            p[++m]=q;
            u[m]=q;
        }
        for(long long i=1;i<=m;i++){
            if(p[i]>z[q] || p[i]>n/q) break;
            z[p[i]*q]=p[i];
        }
    }
    while(t--)
    {
        cin>>q;
        cout<<u[q]<<endl;
    }
    return 0; 
}

by light_searcher @ 2024-10-04 12:30:01

@AC_bee 数据范围到 10^8。

by light_searcher @ 2024-10-04 12:31:36

@AC_bee 然后你的欧拉筛写的有问题

by light_searcher @ 2024-10-04 12:37:37

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e8+5;
int n,p[MAXN/10],m,q;
bool z[MAXN];
int t;
int main(){
    scanf("%d%d",&n,&t);
    for(long long q=2;q<=n;q++){
        if(z[q]==0) p[++m]=q;
        for(long long i=1;i<=m;i++){
            if(p[i]>n/q) break;
            z[p[i]*q]=1;
            if(q%p[i]==0) break;
        }
    }
    while(t--)
    {
        scanf("%d",&q);
        printf("%d\n",p[q]);
    }
    return 0; 
}

by AC_bee @ 2024-10-04 12:54:22

感谢，已关