usaco1.52Prime Palindromes

dfs搜前5位数根据前面的算后面的
View Code
  1 /*
  2  ID: your_id_here
  3  PROG: pprime
  4  LANG: C++
  5  */
  6 #include <iostream>
  7 #include<cstdio>
  8 #include<cstring>
  9 #include<cmath>
 10 #include<algorithm>
 11 using namespace std;
 12 int a,b,g;
 13 int kk[10000],f[20][20],tt,ff[100000];
 14 char s[20];
 15 int prime(int x)
 16 {
 17     int i,j,k,flag = 1;
 18     k = sqrt(x);
 19     for(i = 2 ; i <= k ; i++)
 20     {
 21         if(x%i==0)
 22         {
 23             flag = 0;
 24             break;
 25         }
 26     }
 27     return flag;
 28 }
 29 int palind(int k,char *ss)
 30 {
 31     int i,flag = 1;
 32     for(i = 1; i <= k ;i++)
 33     if(ss[i]!=ss[k-i+1])
 34     {
 35         flag = 0;
 36         break;
 37     }
 38     return flag;
 39 }
 40 void dfs(int v)
 41 {
 42     int i,y,s1 =0,s2 =0,s3 = 0,j;
 43     char str[20],str3[20];
 44     if(v>5)
 45     return ;
 46     for(i = 1; i <= v ; i++)
 47     str[i] = s[i];
 48     for(i = 1; i <= v ; i++)
 49     str3[i] = s[i];
 50     j = v;
 51     for(i = v+1 ; i <= 2*v ; i++)
 52     str[i] = s[j--];
 53     j = v-1;
 54     for(i = v+1 ; i < 2*v ; i++)
 55     str3[i] = s[j--];
 56     y = 1;
 57     for(i = v; i >= 1 ; i--)
 58     {
 59         s1+=y*(s[i]-'0');
 60         y = y*10;
 61     }
 62     y = 1;
 63     for(i = 2*v ; i >= 1 ; i--)
 64     {
 65         s2+=y*(str[i]-'0');
 66         y = y*10;
 67     }
 68     y = 1;
 69     for(i = 2*v-1 ; i >= 1 ; i--)
 70     {
 71         s3+=y*(str3[i]-'0');
 72         y = y*10;
 73     }
 74     if(s1>=a&&s1<=b)
 75     {
 76         if(palind(v,s)&&prime(s1))
 77         {
 78             if(s1<100000)
 79             {
 80                 if(!ff[s1])
 81                 {
 82                     g++;
 83                     kk[g] = s1;
 84                     ff[s1] = 1;
 85                 }
 86             }
 87             else
 88             {
 89                 g++;
 90                 kk[g] = s1;
 91             }
 92         }
 93     }
 94     if(s2>=a&&s2<=b)
 95     {
 96         if(palind(2*v,str)&&prime(s2))
 97         {
 98             if(s2<100000)
 99             {
100                 if(!ff[s2])
101                 {
102                     g++;
103                     kk[g] = s2;
104                     ff[s2] = 1;
105                 }
106             }
107             else
108             {
109 
110                 g++;
111                 kk[g] = s2;
112             }
113         }
114     }
115     if(s3>=a&&s3<=b)
116     {
117         if(palind(2*v-1,str3)&&prime(s3))
118         {
119 
120             if(s3<100000)
121             {
122                 if(!ff[s3])
123                 {
124                     g++;
125                     kk[g] = s3;
126                     ff[s3] = 1;
127                 }
128             }
129             else
130             {
131                 g++;
132                 kk[g] = s3;
133             }
134         }
135     }
136     if(s1>b)
137     return ;
138     for(i = 0 ; i <= 9 ; i++)
139     {
140         s[v+1] = i+'0';
141         dfs(v+1);
142     }
143 }
144 int main()
145 {
146     freopen("pprime.in","r",stdin);
147     freopen("pprime.out","w",stdout);
148     int i;
149     char num[20];
150     cin>>a>>b;
151     for(i = 1; i <= 9 ; i++)
152     {
153         s[1] = i+'0';
154         dfs(1);
155     }
156     sort(kk+1,kk+g+1);
157     for(i = 1; i <= g ; i++)
158     cout<<kk[i]<<endl;
159     fclose(stdin);
160     fclose(stdout);
161     return 0;
162 }