蒟蒻求助最后一点为什么WA

P1217 [USACO1.5] 回文质数 Prime Palindromes

wjk20050306 @ 2022-11-25 16:59:37

#include<bits/stdc++.h>
using namespace std;
bool vis[99989010];
int table[99989010],cnt;
void Pprime(){
    vis[1]=1;
    for(int i=2;i<=99989010;i++){
        if(!vis[i]) table[++cnt]=i;
        for(int j=1;j<=cnt;j++){
            if(i*table[j]>99989010) break;
            vis[i*table[j]]=1;
            if(i%table[j]==0) break;
        }
    }
}
int a,b,k,ans[99989010];
bool ck(int p){
    if(p>=a&&p<=b&&!vis[p]) return 1;
    else return 0;
}
int main(){
    Pprime();
    scanf("%d%d",&a,&b);
    for(int i=1;i<=9;i+=2){
        int t0=10*i+i;
        if(ck(i)) ans[k++]=i;
        if(ck(t0)) ans[k++]=t0;
        if(b>100){
            for(int j=0;j<=9;j++){
                int t1=100*i+10*j+i;
                int t2=1000*i+100*j+10*j+i;
                if(ck(t1)) ans[k++]=t1;
                if(ck(t2)) ans[k++]=t2;
                if(b>10000){
                    for(int jf=0;jf<=9;jf++){
                        int t3=10000*i+1000*j+100*jf+10*j+i;
                        int t4=100000*i+10000*j+1000*jf+100*jf+10*j+i;
                        if(ck(t3)) ans[k++]=t3;
                        if(ck(t4)) ans[k++]=t4;
                        if(b>1000000){
                            for(int j2=0;j2<=9;j2++){
                                int t5=1000000*i+100000*j+10000*jf+1000*j2+100*jf+10*j+i;
                                int t6=10000000*i+1000000*j+100000*jf+10000*j2+1000*j2+100*jf+10*j+i;
                                if(ck(t5)) ans[k++]=t5;
                                if(ck(t6)) ans[k++]=t6; 
                            }   
                        }
                    }
                }
            }
        }
    }
    sort(ans,ans+k);
    for(int i=0;i<k;i++){
        if(ans[i]>=a&&ans[i]<=b) printf("%d\n",ans[i]);
    }
    return 0;
}

大概思路就是欧拉筛,然后构造回文数(枚举) 不知道最后一个点是少了哪个范围或特判吗


by wjk20050306 @ 2022-11-25 17:06:36

妹事了,原来数组开小了


|