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 ————————————————————————题解
其实这又是一道搜索顺序至关重要的搜索题
计算机比人脑强大的地方就是能做大量重复的复杂运算
我们发现主对角线其实影响最大，然后是次对角线，然后逐渐再将限制较多的行或列填上，例如最后一行或者最后一列的数必须是1,3,7,9
预处理出所有5位、各数位的和为n的素数。
按照这样的搜索顺序
1 4 6 5 2
8 1 7 2 8
10 4 1 5 10
9 2 7 1 9
2 3 3 3 1
这样我们可以就可以少打几个循环了……
在计算素数的时候同时求一些一些数位固定的数
【其中XYZ为已知数，.为未知数，_ 为1，3,7,9】
例如枚举1，X ... _
枚举2，_ . X . _
枚举3，X_ _ _ Y
枚举4,5 .X . Y Z
6可以直接计算
枚举7 X . Y . Z
枚举8，9 . X Y Z _
10可以直接计算
然后时限为2s的题就可以0.011过了
/*
LANG: C++
PROG: prime3
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define siji(i,x,y) for(int i=(x); i<=(y) ; ++i)
#define gongzi(j,x,y) for(int j=(x); j>=(y) ; --j)
#define ivorysi
using namespace std;
int n,fi;
int p[][],sum,prime[],tot,all;
bool noprime[];
typedef struct {
int l,r[];
}RECORD200;
/*typedef struct {
int l,r[50];
}RECORD50;*/
typedef struct {
int l,r[];
}RECORD20;
//.0-9 _ 1.3.7.9 - non-zero
RECORD200 pat1[];//X..._ 4*10*10
RECORD200 pat2[];//_.X._ 4*4*10
RECORD20 pat3[][];//X___Y 4*4
RECORD20 pat4[][][];//-X.YZ 9
RECORD20 pat7[][][];//X.Y.Z 10
RECORD20 pat8[][][];//.XYZ_ 4
string sol[];
int marks[][];
bool check(int x) {
if(x%== || x%==) return ;
return ;
}
void makeprime() {
siji(i,,) {
if(!noprime[i]) {
prime[++tot]=i;
if(i>) {
int temp=;
for(int k=;k<=;k*=) {
temp+=i/k%;
}
if(temp==n) {
++sum;
for(int k=,m=;k<= && m>=;k*=,--m) {
p[sum][m]=i/k%;
}
int t1,t2,t3,t4,t5;
t1=p[sum][],t2=p[sum][],t3=p[sum][],t4=p[sum][],t5=p[sum][];
pat1[t1].r[++pat1[t1].l]=sum;
if(check(t1)) pat2[t3].r[++pat2[t3].l]=sum;
if(check(t2)&&check(t3)&&check(t4)) {
pat3[t1][t5].r[++pat3[t1][t5].l]=sum;
}
pat4[t2][t4][t5].r[++pat4[t2][t4][t5].l]=sum;
pat7[t1][t3][t5].r[++pat7[t1][t3][t5].l]=sum;
pat8[t2][t3][t4].r[++pat8[t2][t3][t4].l]=sum;
}
}
}
for(int j=;j<=tot && i</prime[j];++j) {
noprime[prime[j]*i]=;
if(i%prime[j]==) break;
}
}
}
void addsolution() {
++all;
siji(i,,) {
siji(j,,) {
sol[all].append(,marks[i][j]+'');
}
}
}
int num(int x) {
int res=;
siji(i,,) res=res*+p[x][i];
return res;
}
void solve() {
scanf("%d%d",&n,&fi);
makeprime();
int us,tj,tk,tm,tw,ty,tx,tq,temp,temp1,temp2;
for(int i=;i<=pat1[fi].l;++i) {
memset(marks,,sizeof(marks));
us=pat1[fi].r[i];
siji(iv,,) marks[iv][iv]=p[us][iv];
tj=pat2[marks[][]].l;
for(int j=;j<=tj;++j) {
us=pat2[marks[][]].r[j];
siji(iv,,) marks[-iv+][iv]=p[us][iv];
tk=pat3[marks[][]][marks[][]].l;
for(int k=;k<=tk;++k) {
us=pat3[marks[][]][marks[][]].r[k];
siji(iv,,) marks[][iv]=p[us][iv];
tm=pat4[marks[][]][marks[][]][marks[][]].l;
for(int m=;m<=tm;++m) {
us=pat4[marks[][]][marks[][]][marks[][]].r[m];
marks[][]=p[us][];
marks[][]=p[us][];
tw=pat4[marks[][]][marks[][]][marks[][]].l;
for(int w=;w<=tw;++w) {
us=pat4[marks[][]][marks[][]][marks[][]].r[w];
marks[][]=p[us][];
marks[][]=p[us][];
marks[][]=;
temp=;
siji(iv,,) temp+=marks[][iv];
marks[][]=n-temp;
if(marks[][]< || marks[][]>) continue;
temp=;
siji(iv,,) {
temp=temp*+marks[][iv];
}
if(noprime[temp]) continue;
ty=pat7[marks[][]][marks[][]][marks[][]].l;
for(int y=;y<=ty;++y) {
us=pat7[marks[][]][marks[][]][marks[][]].r[y];
marks[][]=p[us][];
marks[][]=p[us][];
tx=pat8[marks[][]][marks[][]][marks[][]].l;
for(int x=;x<=tx;++x) {
us=pat8[marks[][]][marks[][]][marks[][]].r[x];
marks[][]=p[us][];
marks[][]=p[us][];
tq=pat8[marks[][]][marks[][]][marks[][]].l;
for(int q=;q<=tq;++q) {
us=pat8[marks[][]][marks[][]][marks[][]].r[q];
marks[][]=p[us][];
marks[][]=p[us][];
marks[][]=marks[][]=;
temp1=temp2=;
siji(iv,,) temp1+=marks[iv][],temp2+=marks[iv][];
marks[][]=n-temp1;marks[][]=n-temp2;
if(marks[][]< || marks[][]< ||marks[][]> || marks[][]>)
continue;
temp1=temp2=;
siji(iv,,)
temp1=temp1*+marks[iv][],temp2=temp2*+marks[iv][];
if(noprime[temp1]||noprime[temp2]) continue;
temp1=temp2=;
siji(iv,,)
temp1=temp1*+marks[][iv],temp2+=marks[][iv];
if(noprime[temp1] || temp2!=n) continue;
addsolution();
}
}
}
}
}
}
}
}
if(all==) puts("NONE");
sort(sol+,sol+all+);
siji(i,,all) {
for(int j=;j<;++j) {
cout<<sol[i].substr(j*,)<<endl;
}
if(i!=all) puts("");
}
}
int main(int argc, char const *argv[])
{
#ifdef ivorysi
freopen("prime3.in","r",stdin);
freopen("prime3.out","w",stdout);
#else
freopen("f1.in","r",stdin);
freopen("f1.out","w",stdout);
#endif
solve();
return ;
}