USACO 1.5 Prime Palindromes(枚举）

news/2024/7/8 7:31:22 标签: c/c++

本来想筛选素数的。。。交了之后发现复杂度也太高了。。。可耻的看了一下hint，然后就各种for枚举了每一位了。.。

  1 /*
  2 ID: cuizhe
  3 LANG: C++
  4 TASK: pprime
  5 */
  6 #include <cstdio>
  7 #include <cstring>
  8 #include <cmath>
  9 #include <algorithm>
 10 using namespace std;
 11 #define N 1000001
 12 bool p[N];
 13 int prim[100000],num;
 14 int judge(int x)
 15 {
 16     int i;
 17     for(i = 1;i <= num-1;i ++)
 18     {
 19         if(prim[i] > x)
 20         break;
 21         if(x%prim[i] == 0)
 22         return 0;
 23     }
 24     return 1;
 25 }
 26 int main()
 27 {
 28     int i,j,k,u;
 29     long long t,a,b;
 30     freopen("pprime.in","r",stdin);
 31     freopen("pprime.out","w",stdout);
 32     scanf("%lld%lld",&a,&b);
 33     for(i = 2; i <= N; i ++)
 34     {
 35         if(!p[i])
 36         {
 37             for(j = i+i; j <= N; j += i)
 38             {
 39                 p[j] = 1;
 40             }
 41         }
 42     }
 43     num = 1;
 44     for(i = 2;i <= N;i ++)
 45     {
 46         if(!p[i])
 47         prim[num++] = i;
 48     }
 49     for(i = 1;i <= 9;i += 2)//一位
 50     {
 51         if(!p[i]&&i >= a&&i <= b)
 52         printf("%d\n",i);
 53     }
 54     for(i = 1;i <= 9;i += 2)//两位
 55     {
 56         if(!p[i*10+i]&&i*10+i>=a&&i*10+i<=b)
 57         printf("%d\n",i*10+i);
 58     }
 59     for(i = 1;i <= 9;i += 2)//三位
 60     {
 61         for(j = 0;j <= 9;j ++)
 62         {
 63             if(!p[i*100+j*10+i]&&i*100+j*10+i>=a&&i*100+j*10+i<=b)
 64             printf("%d\n",i*100+j*10+i);
 65         }
 66     }
 67     for(i = 1;i <= 9;i += 2)//四位
 68     {
 69         for(j = 0;j <= 9;j ++)
 70         {
 71             if(!p[i*1000+j*100+10*j+i]&&i*1000+j*100+10*j+i>=a&&i*1000+j*100+10*j+i<=b)
 72             printf("%d\n",i*100+j*100+10*j+i);
 73         }
 74     }
 75     for(i = 1;i <= 9;i += 2)//五位
 76     {
 77         for(j = 0;j <= 9;j ++)
 78         {
 79            for(k = 0;k <= 9;k ++)
 80            {
 81                t = i*10000+i+1000*j+10*j+k*100;
 82                if(!p[t]&&t>=a&&t<=b)
 83                printf("%lld\n",t);
 84            }
 85         }
 86     }
 87     for(i = 1;i <= 9;i += 2)//六位
 88     {
 89         for(j = 0;j <= 9;j ++)
 90         {
 91            for(k = 0;k <= 9;k ++)
 92            {
 93                t = i*100000+i+10000*j+10*j+k*1000+k*100;
 94                if(!p[t]&&t >= a&&t <= b)
 95                printf("%lld\n",t);
 96            }
 97         }
 98     }
 99     for(i = 1;i <= 9;i += 2)//七位
100     {
101         for(j = 0;j <= 9;j ++)
102         {
103             for(k = 0;k <= 9;k ++)
104             {
105                 for(u = 0;u <= 9;u ++)
106                 {
107                     t = 1000000*i+i+100000*j+10*j+10000*k+k*100+1000*u;
108                     if(judge(t)&&t >= a&&t <= b)
109                     printf("%lld\n",t);
110                 }
111             }
112         }
113     }
114     for(i = 1;i <= 9;i += 2)//八位
115     {
116         for(j = 0;j <= 9;j ++)
117         {
118             for(k = 0;k <= 9;k ++)
119             {
120                 for(u = 0;u <= 9;u ++)
121                 {
122                     t = 10000000*i+i+1000000*j+10*j+100000*k+k*100+10000*u+1000*u;
123                     if(judge(t)&&t >= a&&t <= b)
124                     printf("%lld\n",t);
125                 }
126             }
127         }
128     }
129     return 0;
130 }