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] < 0) continue;
197 if (map[1][2] > 9 || map[3][2] > 9 || map[2][1] > 9 || map[2][3] > 9) continue;
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一下