USACO6.4-The Primes

The Primes
IOI'94

In the square below, each row, each column and the two diagonals can be read as a five digit prime number. The rows are read from left to right. The columns are read from top to bottom. Both diagonals are read from left to right. 

+---+---+---+---+---+
| 1 | 1 | 3 | 5 | 1 |
+---+---+---+---+---+
| 3 | 3 | 2 | 0 | 3 |
+---+---+---+---+---+
| 3 | 0 | 3 | 2 | 3 |
+---+---+---+---+---+
| 1 | 4 | 0 | 3 | 3 |
+---+---+---+---+---+
| 3 | 3 | 3 | 1 | 1 |
+---+---+---+---+---+
  • The prime numbers' digits must sum to the same number.
  • The digit in the top left-hand corner of the square is pre-determined (1 in the example).
  • A prime number may be used more than once in the same square.
  • If there are several solutions, all must be presented (sorted in numerical order as if the 25 digits were all one long number).
  • A five digit prime number cannot begin with a zero (e.g., 00003 is NOT a five digit prime number).

PROGRAM NAME: prime3

INPUT FORMAT

A single line with two space-separated integers: the sum of the digits and the digit in the upper left hand corner of the square.

SAMPLE INPUT (file prime3.in)

11 1

OUTPUT FORMAT

Five lines of five characters each for each solution found, where each line in turn consists of a five digit prime number. Print a blank line between solutions. If there are no prime squares for the input data, output a single line containing "NONE".

SAMPLE OUTPUT (file prime3.out)

The above example has 3 solutions.

11351
14033
30323
53201
13313

11351
33203
30323
14033
33311

13313
13043
32303
50231
13331

题目大意：给出一个5*5的正方形和左上角的一个数字，要求每一行每一列每一对角线上的数字的和都等于输入的数，并且组成的五位数为质数，输出所有可能的5*5正方形。

算法：这是一道很麻烦的暴力题，朴素的枚举必定会超时，这时候需要调换枚举顺序，以及根据枚举的五位数的位置尽可能排除不可能的情况再枚举，要优化的地方还是比较多的，详见代码。

  1 #include <iostream>
  2 #include <memory.h>
  3 #include <stdio.h>
  4 #include <vector>
  5 #include <string>
  6 #include <algorithm>
  7 using namespace std;
  8 #define MAXN 100000
  9 #define R 0
 10 #define C 1
 11 
 12 
 13 void output(string str)
 14 {
 15     for(int i=0; i<str.length(); i++)
 16     {
 17         printf("%c",str[i]);
 18         if(i%5==4)
 19             printf("
");
 20     }
 21 }
 22 
 23 int getDigSum(int x)
 24 {
 25     int sum=0;
 26     while(x!=0)
 27     {
 28         sum+=x%10;
 29         x/=10;
 30     }
 31     return sum;
 32 }
 33 
 34 bool allDigOdd(int x)
 35 {
 36     while(x!=0)
 37     {
 38         int dig=x%10;
 39         if(dig%2==0)
 40             return false;
 41         x/=10;
 42     }
 43     return true;
 44 }
 45 
 46 bool allNoZero(int x)
 47 {
 48     while(x!=0)
 49     {
 50         int dig=x%10;
 51         if(dig==0)
 52             return false;
 53         x/=10;
 54     }
 55     return true;
 56 }
 57 
 58 int isPrime[MAXN+10],primeDig[MAXN+10][5];
 59 
 60 int a[5][5]= {0},goalSum=0,st;
 61 vector<int> primelist[100]; // 以d[ij]表示以i开头，j结尾的字符串
 62 vector<int> primelistMid[1000]; // 以d[ijk]表示以i开头，j为百位，k结尾的字符串
 63 vector<int> primelistOdd[100]; // 各位上的数都为奇数
 64 vector<int> primelistnozero[100]; // 各位上都没有0
 65 vector<string> res;
 66 
 67 int isprime(int type,int num)
 68 {
 69 
 70     int sum=0;
 71     if(type==R)
 72     {
 73         for(int i=0; i<5; i++)
 74             sum=sum*10+a[num][i];
 75     }
 76     else
 77     {
 78         for(int i=0; i<5; i++)
 79             sum=sum*10+a[i][num];
 80     }
 81     return isPrime[sum];
 82 }
 83 
 84 void add()
 85 {
 86     string str;
 87     for(int i=0; i<5; i++)
 88         for(int j=0; j<5; j++)
 89         {
 90             str+='0'+a[i][j];
 91         }
 92     res.push_back(str);
 93 }
 94 
 95 void initA()
 96 {
 97     for(int i=0; i<5; i++)
 98         for(int j=0; j<5; j++)
 99             a[i][j]=100;
100 }
101 
102 int main()
103 {
104     freopen("prime3.in","r",stdin);
105     freopen("prime3.out","w",stdout);
106 
107     initA();
108 
109     // 求素数表
110     memset(isPrime,-1,sizeof isPrime);
111     for(int i=2; i<=MAXN; i++)
112         if(isPrime[i])
113             for(long long j=(long long)i*i; j<=MAXN; j+=i)
114                 isPrime[j]=false;
115 
116 
117     cin>>goalSum>>st;
118 
119     for(int i=10000; i<MAXN; i++)
120         if(isPrime[i] && getDigSum(i)!=goalSum)
121             isPrime[i]=0;
122 
123     for(int i=10000; i<MAXN; i++)
124         if(isPrime[i])
125         {
126             int x=i;
127             for(int j=0; j<5; j++)
128             {
129                 primeDig[i][4-j]=x%10;
130                 x/=10;
131             }
132             primelist[i/10000*10+i%10].push_back(i);
133             primelistMid[i/10000*100+(i%1000)/100*10+i%10].push_back(i);
134         }
135 
136     // 各位上都为奇数
137     for(int i=10000; i<MAXN; i++)
138         if(isPrime[i] && allDigOdd(i))
139             primelistOdd[i/10000*10+i%10].push_back(i);
140 
141     // 各位上都为非0
142     for(int i=10000; i<MAXN; i++)
143         if(isPrime[i] && allNoZero(i))
144             primelistnozero[i/10000*10+i%10].push_back(i);
145 
146     bool found=false;
147 
148     a[0][0]=st;
149     // 枚举 先是右下方数字
150     for(a[4][4]=1; a[4][4]<=9; a[4][4]+=2)
151     {
152         // 枚举左下方数字
153         for(a[4][0]=1; a[4][0]<=9; a[4][0]+=2)
154         {
155             // 枚举右上方数字
156             for(a[0][4]=1; a[0][4]<=9; a[0][4]+=2)
157             {
158                 //填充左边质数
159                 for(int i=0; i<primelistnozero[st*10+a[4][0]].size(); i++)
160                 {
161                     for(int j=0; j<5; j++)
162                         a[j][0]=primeDig[primelistnozero[st*10+a[4][0]][i]][j];
163 
164                     // 填充上边质数
165                     for(int ii=0; ii<primelistnozero[st*10+a[0][4]].size(); ii++)
166                     {
167                         for(int j=0; j<5; j++)
168                             a[0][j]=primeDig[primelistnozero[st*10+a[0][4]][ii]][j];
169 
170 
171                         // 填充下边质数
172                         for(int iii=0; iii<primelistOdd[a[4][0]*10+a[4][4]].size(); iii++)
173                         {
174                             for(int j=0; j<5; j++)
175                                 a[4][j]=primeDig[primelistOdd[a[4][0]*10+a[4][4]][iii]][j];
176 
177 
178                             //填充右边质数
179                             for(int iiii=0; iiii<primelistOdd[a[0][4]*10+a[4][4]].size(); iiii++)
180                             {
181                                 for(int j=0; j<5; j++)
182                                     a[j][4]=primeDig[primelistOdd[a[0][4]*10+a[4][4]][iiii]][j];
183 
184 
185                                 // 填充中间一点
186                                 for(a[2][2]=0; a[2][2]<=9; a[2][2]++)
187                                 {
188 
189                                     // 填充主对角线
190                                     for(int k=0; k<primelistMid[st*100+a[2][2]*10+a[4][4]].size(); k++)
191                                     {
192                                         a[1][1]=primeDig[primelistMid[st*100+a[2][2]*10+a[4][4]][k]][1];
193                                         a[3][3]=primeDig[primelistMid[st*100+a[2][2]*10+a[4][4]][k]][3];
194 
195                                         // 填充辅对角线
196                                         for(int l=0; l<primelistMid[a[4][0]*100+a[2][2]*10+a[0][4]].size(); l++)
197                                         {
198                                             a[3][1]=primeDig[primelistMid[a[4][0]*100+a[2][2]*10+a[0][4]][l]][1];
199                                             a[1][3]=primeDig[primelistMid[a[4][0]*100+a[2][2]*10+a[0][4]][l]][3];
200 
201                                             int a12=goalSum-(a[1][0]+a[1][1]+a[1][3]+a[1][4]);
202                                             int a21=goalSum-(a[0][1]+a[1][1]+a[3][1]+a[4][1]);
203                                             int a23=goalSum-(a[0][3]+a[1][3]+a[3][3]+a[4][3]);
204                                             int a32=goalSum-(a[3][0]+a[3][1]+a[3][3]+a[3][4]);
205                                             a[1][2]=a12;
206                                             a[2][1]=a21;
207                                             a[2][3]=a23;
208                                             a[3][2]=a32;
209                                             if(a12>=0 && a12<10 && a21>=0 && a21<10 && a23>=0 && a23<10 && a32>=0 && a32<10
210                                                     && isprime(R,1) && isprime(R,2) && isprime(R,3)
211                                                     && isprime(C,1) && isprime(C,2) && isprime(C,3))
212                                             {
213                                                 found=true;
214                                                 add();
215                                             }
216                                         }
217 
218                                     }
219                                 }
220 
221                             }
222                         }
223                     }
224                 }
225             }
226         }
227     }
228 
229     sort(res.begin(),res.end());
230     bool first=true;
231     for(int i=0; i<res.size(); i++)
232     {
233         if(!first)
234         {
235             cout<<endl;
236         }
237         first=false;
238         output(res[i]);
239     }
240 
241     if(!found)
242         printf("NONE
");
243     return 0;
244 }





        

	      

	    

	  

	  

	    
      
        【推广】
        免费学中医，健康全家人
      
	  

    

    

          原文地址：https://www.cnblogs.com/oneshot/p/4121954.html