1 import java.io.*;
  2 import java.util.*;
  3 /*
  4 ID: yanglei4
  5 LANG: JAVA
  6 TASK:prime3
  7 */
  8 public class prime3{
  9     static boolean[] prime = new boolean[100001];
 10     static int[] digit = new int[100001];
 11     
 12     public static void main(String[] args) throws IOException {
 13         BufferedReader fin = new BufferedReader(new FileReader("prime3.in"));
 14         PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("prime3.out")));
 15         StringTokenizer st = new StringTokenizer(fin.readLine());
 16         int sum = Integer.parseInt(st.nextToken());
 17         int upperleft = Integer.parseInt(st.nextToken());
 18         int totalcount = 0;
 19         ArrayList<String> result = new ArrayList<String>();
 20         
 21         if (sum % 3 == 0) {
 22             out.println("NONE");
 23         } 
 24         else {
 25 
 26             
 27             //Find the primes first
 28             Arrays.fill(prime, true);
 29             for (int i = 0; i < 100000; i++)
 30                 if (i % 2 == 0)
 31                     prime[i] = false;
 32             prime[1= false;
 33             prime[2= true;
 34             
 35             for(int i = 3; i <= 1000; i += 2 )
 36                 if(prime[i])
 37                     for(int j = i + i; j <= 100000; j += i ) prime[j] = false;
 38             
 39             //count the digit
 40             for (int i = 10001; i <= 99997; i++)
 41                 if (prime[i]) {
 42                     int temp = i;
 43                     int tempsum = 0;
 44                     while (temp != 0) {
 45                         tempsum += temp % 10;
 46                         temp /= 10;
 47                     }
 48                     digit[i] = tempsum;
 49                 }
 50            
 51             int[] numbers = new int[100000];
 52             int count = 0;
 53             for (int i = 10001; i <= 99997; i++) {
 54                 if (prime[i] && digit[i] == sum)
 55                     numbers[count++= i;
 56             }
 57             
 58             int[] line5 = new int[100000];
 59             int countline5 = 0;
 60             for (int i = 0; i < count; i++) {
 61                 int temp = numbers[i];
 62                 boolean flag = true;
 63                 while (temp != 0) {
 64                     int dit = temp % 10;
 65                     if (dit == 0 || dit == 2 || dit == 4 || dit ==5 || dit == 6 || dit == 8) {
 66                         flag = false;
 67                         break;
 68                     }
 69                     temp /= 10;
 70                 }
 71                 if (flag) line5[countline5++= numbers[i];
 72             }
 73            // for (int i = 0; i < countline5; i++) System.out.println("* " + line5[i]);
 74             
 75             int[] line1 = new int[100000];
 76             int countline1 = 0;
 77             for (int i = 0; i < count; i++) {
 78                 int firstdit = numbers[i] / 10000;
 79                 int seconddit = numbers[i] / 1000 % 10;
 80                 int thirddit = numbers[i] / 100 % 10;
 81                 int fourthdit = numbers[i] / 10 % 10;
 82                 if (firstdit == upperleft && seconddit != 0 && thirddit != 0 && fourthdit != 0
 83                     line1[countline1++= numbers[i];    
 84             }
 85             
 86             boolean[][] firstfifth = new boolean[10][10];
 87             boolean[][] secondfifth = new boolean[10][10];
 88             boolean[][] thirdfifth = new boolean[10][10];
 89             boolean[][] fourthfifth = new boolean[10][10];
 90             boolean[][][] secondfourthfifth = new boolean[10][10][10];
 91             boolean[][][][] firstsecondfourthfifth = new boolean[10][10][10][10];
 92             
 93             for (int i = 0; i < count; i++
 94                 {
 95                     int firstdit = numbers[i] / 10000;
 96                     int seconddit = numbers[i] / 1000 % 10;
 97                     int thirddit = numbers[i] / 100 % 10;
 98                     int fourthdit = numbers[i] / 10 % 10;
 99                     int fifthdit = numbers[i] % 10;
100                     firstfifth[firstdit][fifthdit] = true;
101                     secondfifth[seconddit][fifthdit] = true;
102                     thirdfifth[thirddit][fifthdit] = true;
103                     fourthfifth[fourthdit][fifthdit] = true;
104                     secondfourthfifth[seconddit][fourthdit][fifthdit] = true;
105                     firstsecondfourthfifth[firstdit][seconddit][fourthdit][fifthdit] = true;
106                 }
107     
108             //Start
109             int[][] map = new int[5][5];
110             map[0][0= upperleft;
111             
112             int temp = 0;
113             //row 5
114             for (int a = 0; a < countline5; a++) {
115                 temp = line5[a];
116                 for (int k = 4; k >= 0; k--) {
117                     map[4][k] = temp % 10;
118                     temp /= 10;
119                 }
120                 
121                 //column 5
122                 for (int b = 0; b < countline5; b++
123                     if (map[4][4== line5[b] % 10) {    
124                         temp = line5[b];
125                         for (int k = 4; k >= 0; k--) {
126                             map[k][4= temp % 10;
127                             temp /= 10;
128                         }
129                         
130                         
131                         //main dig
132                         for (int c = 0; c < count; c++
133                             if (map[4][0== numbers[c] / 10000 && map[0][4== numbers[c] % 10) {
134                                 
135                                 int seconddit = numbers[c] / 1000 % 10;
136                                 int thirddit = numbers[c] / 100 % 10;
137                                 int fourthdit = numbers[c] / 10 % 10;
138                                 if (secondfifth[seconddit][map[3][4]] == true &&
139                                         fourthfifth[seconddit][map[4][1]] == true &&
140                                         thirdfifth[thirddit][map[2][4]] == true &&
141                                         thirdfifth[thirddit][map[4][2]] == true &&
142                                         fourthfifth[fourthdit][map[1][4]] == true &&
143                                         secondfifth[fourthdit][map[4][3]] == true) {
144                                         map[3][1= seconddit;
145                                         map[2][2= thirddit;
146                                         map[1][3= fourthdit;
147                         
148                                         
149                                         //second dig    
150                                         for (int d = 0; d < count; d++
151                                             if (numbers[d] / 10000 == upperleft && numbers[d] % 10 == map[4][4&& numbers[d] / 100 % 10 == map[2][2]) {
152                                                         
153                                                         seconddit = numbers[d] / 1000 % 10;
154                                                         fourthdit = numbers[d] / 10 % 10;
155                                                         if (secondfourthfifth[seconddit][map[3][1]][map[4][1]] == true && 
156                                                                 secondfourthfifth[seconddit][map[1][3]][map[1][4]] == true &&
157                                                                 secondfourthfifth[map[3][1]][fourthdit][map[3][4]] == true &&
158                                                                 secondfourthfifth[map[1][3]][fourthdit][map[4][3]] == true) {
159                                                             map[1][1= seconddit;
160                                                             map[3][3= fourthdit;
161                                                             
162                                                             //first row
163                                                             for (int e = 0; e < countline1; e++
164                                                                 if (line1[e] % 10 == map[0][4]) {
165                                                                     seconddit = line1[e] / 1000 % 10;
166                                                                     thirddit = line1[e] / 100 % 10;
167                                                                     fourthdit = line1[e] / 10 % 10;
168                                                                     if (firstsecondfourthfifth[seconddit][map[1][1]][map[3][1]][map[4][1]] == false ||
169                                                                             firstsecondfourthfifth[fourthdit][map[1][3]][map[3][3]][map[4][3]] == false)
170                                                                                 continue;
171                                                                                 
172                                                                     map[0][1= seconddit;
173                                                                     map[0][2= thirddit;
174                                                                     map[0][3= fourthdit;
175                                                                     
176                                                                     //first column
177                                                                     for (int f = 0; f < countline1; f++
178                                                                         if (line1[f] % 10 == map[4][0]) {
179                                                                             seconddit = line1[f] / 1000 % 10;
180                                                                             thirddit = line1[f] / 100 % 10;
181                                                                             fourthdit = line1[f] / 10 % 10;
182                                                                             if (firstsecondfourthfifth[seconddit][map[1][1]][map[1][3]][map[1][4]] == false ||
183                                                                                     firstsecondfourthfifth[fourthdit][map[3][1]][map[3][3]][map[3][4]] == false)
184                                                                                         continue;                                                                            
185                                                                             map[1][0= seconddit;
186                                                                             map[2][0= thirddit;
187                                                                             map[3][0= fourthdit;
188                                                                             
189                                                                             //left four digit
190                                                                             map[1][2= sum - map[1][0- map[1][1- map[1][3- map[1][4];
191                                                                             map[3][2= sum - map[3][0- map[3][1- map[3][3- map[3][4];
192                                                                             map[2][1= sum - map[0][1- map[1][1- map[3][1- map[4][1];
193                                                                             map[2][3= sum - map[0][3- map[1][3- map[3][3- map[4][3];
194 
195                                                                             //check
196                                                                             if (map[1][2< 0 || map[3][2< 0 || map[2][1< 0 || map[2][3< 0continue;
197                                                                             if (map[1][2> 9 || map[3][2> 9 || map[2][1> 9 || map[2][3> 9continue;
198                                                                             
199                                                                             int tempsum = 0;
200                                                                             
201                                                                             for (int k = 0; k < 5; k++) tempsum += map[2][k];
202                                                                             if (tempsum != sum) continue;
203                                                                             
204                                                                             tempsum = 0;
205                                                                             for (int k = 0; k < 5; k++) tempsum += map[k][2];
206                                                                             if (tempsum != sum) continue;
207                                                                             
208         
209                                                                             tempsum = 0;
210                                                                             //row 2
211                                                                             for (int k = 0; k < 5; k++) tempsum = tempsum * 10 + map[1][k];
212                                                                             if (tempsum <= 99999 && !prime[tempsum]) continue;
213                                                                             
214                                                                             //row 3
215                                                                             tempsum = 0;
216                                                                             for (int k = 0; k < 5; k++) tempsum = tempsum * 10 + map[2][k];
217                                                                             if (tempsum <= 99999 && !prime[tempsum]) continue;        
218                                                                             
219                                                                             //row 4
220                                                                             tempsum = 0;
221                                                                             for (int k = 0; k < 5; k++) tempsum = tempsum * 10 + map[3][k];
222                                                                             if (tempsum <= 99999 && !prime[tempsum]) continue;        
223                                                                             
224                                                                             //column 2
225                                                                             tempsum = 0;
226                                                                             for (int k = 0; k < 5; k++) tempsum = tempsum * 10 + map[k][1];
227                                                                             if (tempsum <= 99999 && !prime[tempsum]) continue;        
228 
229                                                                             //column 3
230                                                                             tempsum = 0;
231                                                                             for (int k = 0; k < 5; k++) tempsum = tempsum * 10 + map[k][2];
232                                                                             if (tempsum <= 99999 && !prime[tempsum]) continue;    
233                                                                             
234                                                                             //column 4
235                                                                             tempsum = 0;
236                                                                             for (int k = 0; k < 5; k++) tempsum = tempsum * 10 + map[k][3];
237                                                                             if (tempsum <= 99999 && !prime[tempsum]) continue;    
238                                                                             
239                                                                             totalcount++;
240                                                                             StringBuffer sb = new StringBuffer();
241                                                                             for (int x = 0; x < 5; x++)
242                                                                                 for (int y = 0; y < 5; y++)
243                                                                                     sb.append(map[x][y]);
244                    
245                                                                             result.add(sb.toString());
246                                                                     }
247                                                                 }
248                                                         }
249                                             }
250                                     
251                                 }
252                             }
253                     }
254             }
255 
256         }
257         
258         if (totalcount > 0) {
259             Collections.sort(result);
260             int tc = 0;
261             for (String x : result) {
262                 if (tc != 0)
263                     out.println();
264                 for (int i = 0; i < 5; i++) {
265                     for (int j = 0; j < 5; j++
266                         out.print(x.charAt(i * 5 + j));
267                     out.println();
268                 }
269                 tc++;
270             }
271             
272         }
273         else
274             out.println("NONE");
275         out.close();
276         System.exit(0);
277     }
278 }
279 


太爽了,这道题目居然用自己的算法过了,真不容易啊,将近300行的代码

 大致说一下我怎么做的吧。

首先,我把0~99999所有的素数全部筛选了出来,用筛选法,应该很快就可以完成。

然后,我把这些素数中,数字和等于um的全部挑选出来,放在numbers里面

因为每行每列的数只有可能是这些number中的一个

我不知道这样做是不是能提前把搜索的范围减小,但是肯定的事这样做能过。

这样之后就是确定搜素顺序,我参考了NOCOW上面的顺序,先第五行,第五列,然后对角线,然后第一行第一列,最后把剩下的四个数用加法算出来。

在这此前,我做了进一步的预处理
首先,第五行(列)中的每个数字都不能是0 2 4 5 6 8,否则的话,该列(行)必然不是素数。我把这些数字预处理出来,放在line5里面
这一步应该能大大减小搜索范围。

然后是对角线,因为对角线的两个端点其实都已经确定了,所以只需要看中间的3个数
比如主对角线,因为左下和右上的数已经填好了,我们就需要从numbers中找出来符合的数填进去。
在这过程中,还可以加上一步剪枝
0 0 0 0 1
0 0 0 c 2
0 0 b 0 3
0 a 0 0 4
1 2 3 4 5

注意你在填a,b,c的时候,其实你已经影响了第二行第二列,第三行第三列,第四行第四列了。

当你在填a的时候,第二列的后两个数就确定了,第四列的2,5数就确定了。
这样的话我们可以去numbers中查找,如果不存在后两个数是a2,和第2,4位是a..4的数,那么就直接continue
至于怎么查找,我们可以在之前预处理,设一个数组secondfifth[][],fourthfifth[][]
然后把所有numbers遍历一遍,把这两个数组初始化,这两个数组第[i][j]表示存在一个素数,第2,5(4,5)位是i,j

同理,副对角线也是可以这样剪枝的。

然后就是第一行,第一列了,以第一行为例。
第一行也是第一个和第五个已经确定了,只需要中间三个就行,我开始没有做剪枝,就是直接把所有的全弄上去了。
结果居然没有过,后来又加了一个剪枝

1 2 3 4 1
0 2 0 4 2
0 0 3 0 3
0 2 0 4 4
1 2 3 4 5

看第二列第四列,跟前面的情况相同,第1,2,4,5位已经确定,于是可以先预处理一个数组,把numbers里面的
每一个的1,2,4,5位提出来,然后把相应的数组位设成是true

第一列也可以这样做。

这样矩阵中就剩下4个数了,[2,3],[3,2],[3,4],[4,3],这样的话,可以用第二列,第四列,第二行,第四行算出来。

然后就是进行最后的check

1、算出来的每个数必须要大于等于0,小于10
2、第2~4行,第2~4列必须是素数

做过这两个之后,剩下的就是满足条件的了。

然后把这个数组存储到一个String里面,等所有的全选好了,再用sort一下