在下面的方格中，每行，每列，以及两条对角线上的数字可以看作是五位的素数。方格中的行按照从左到右的顺序组成一个素数，而列按照从上到下的顺序。两条对角线也是按照从左到右的顺序来组成。
+---+---+---+---+---+
| 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 |
+---+---+---+---+---+
* 这些素数各个数位上的和必须相等。
* 左上角的数字是预先定好的。
* 一个素数可能在方阵中重复多次。
* 如果不只有一个解，将它们全部输出（按照这25个数字组成的25位数的大小排序）。
* 一个五位的素数开头不能为0（例如：00003 不是五位素数）
格式
PROGRAM NAME: prime3
INPUT FORMAT:(file prime3.in)
一行包括两个被空格分开的整数:各数位上的数字的和 以及左上角的数字。
OUTPUT FORMAT:(file prime3.out)
对于每一个找到的方案输出5行，每行5个字符, 每行可以转化为一个5位的质数.在两组方案中间输出一个空行. 如果没有解就单独输出一行"NONE"。
SAMPLE INPUT
11 1
SAMPLE OUTPUT
上面的例子有三组解。
11351
14033
30323
53201
13313
11351
33203
30323
14033
33311
13313
13043
32303
50231
13331
分析：史上最大(最多FOR)的枚举题，堪称经典。
剪枝和搜索顺序是决定AC与否的关键，尤其是搜索顺序，我的变量名已经说明了搜索顺序。
a11代表第一行第一列。
【参考程序】：
/*
ID: XIONGNA1
PROG: prime3
LANG: C++
*/
#include<iostream>
#include<cstring>
using namespace std;
struct node
{
int l1,l2,l3,l4,l5;
} ans[100002];
bool p[100002];
int sum,n,a11;
void makeprime()
{
memset(p,true,sizeof(p));
p[1]=p[0]=false;
for (int i=2;i<=99999;i++)
if (p[i])
for (int j=i;j<=99999/i;j++)
p[i*j]=false;
}
bool check(node a,node b)
{
if (a.l1<b.l1) return true; if (a.l1>b.l1) return false;
if (a.l2<b.l2) return true; if (a.l2>b.l2) return false;
if (a.l3<b.l3) return true; if (a.l3>b.l3) return false;
if (a.l4<b.l4) return true; if (a.l4>b.l4) return false;
if (a.l5<b.l5) return true; if (a.l5>b.l5) return false;
return false;
}
void cout_ans()
{
node tt;
for (int i=1;i<=n-1;i++)
for (int j=i+1;j<=n;j++)
if (check(ans[j],ans[i]))
{
tt=ans[j];ans[j]=ans[i];ans[i]=tt;
}
printf("%d\n%d\n%d\n%d\n%d\n",ans[1].l1,ans[1].l2,ans[1].l3,ans[1].l4,ans[1].l5);
for (int i=2;i<=n;i++)
{
printf("\n");
printf("%d\n%d\n%d\n%d\n%d\n",ans[i].l1,ans[i].l2,ans[i].l3,ans[i].l4,ans[i].l5);
}
}
void for_work()
{
for (int a22=0;a22<=9;a22++)//对角
for (int a33=0;a33<=9;a33++)
for (int a44=0;a44<=9;a44++)
{
int a55=sum-a11-a22-a33-a44;
if (a55==1 || a55==3 || a55==7 || a55==9)
if (p[a11*10000+a22*1000+a33*100+a44*10+a55])
{
for (int a51=1;a51<=9;a51++)//对角
for (int a42=0;a42<=9;a42++)
for (int a24=0;a24<=9;a24++)
{
int a15=sum-a51-a42-a33-a24;
if (a15==1 || a15==3 || a15==7 || a15==9)
if (p[a51*10000+a42*1000+a33*100+a24*10+a15])
{
for (int a12=1;a12<=9;a12++)
for (int a13=1;a13<=9;a13++)
{
int a14=sum-a11-a12-a13-a15;
if (a14>=1 && a14<=9)
if (p[a11*10000+a12*1000+a13*100+a14*10+a15])
{
for (int a32=0;a32<=9;a32++)
{
int a52=sum-a12-a22-a32-a42;
if (a52>=0 && a52<=9)
if (p[a12*10000+a22*1000+a32*100+a42*10+a52])
{
for (int a34=0;a34<=9;a34++)
{
int a54=sum-a14-a24-a34-a44;
int a53=sum-a51-a52-a54-a55;
if (a54>=0 && a54<=9)
if (a53>=0 && a53<=9)
if (p[a51*10000+a52*1000+a53*100+a54*10+a55])
if (p[a14*10000+a24*1000+a34*100+a44*10+a54])
{
for (int a21=1;a21<=9;a21++)
for (int a31=1;a31<=9;a31++)
{
int a41=sum-a11-a21-a31-a51;
int a35=sum-a31-a32-a33-a34;
if (a41>=1 && a41<=9)
if (a35==1 || a35==3 || a35==7 || a35==9)
if (p[a31*10000+a32*1000+a33*100+a34*10+a35])
if (p[a11*10000+a21*1000+a31*100+a41*10+a51])
{
for (int a23=0;a23<=9;a23++)
{
int a25=sum-a21-a22-a23-a24;
int a43=sum-a13-a23-a33-a53;
int a45=sum-a41-a42-a43-a44;
if (a25==1 || a25==3 || a25==7 || a25==9)
if (a43>=0 && a43<=9)
if (a45==1 || a45==3 || a45==7 || a45==9)
{
if (p[a21*10000+a22*1000+a23*100+a24*10+a25])
if (p[a41*10000+a42*1000+a43*100+a44*10+a45])
if (p[a13*10000+a23*1000+a33*100+a43*10+a53])
if (p[a15*10000+a25*1000+a35*100+a45*10+a55])
{
n++;
ans[n].l1=a11*10000+a12*1000+a13*100+a14*10+a15;
ans[n].l2=a21*10000+a22*1000+a23*100+a24*10+a25;
ans[n].l3=a31*10000+a32*1000+a33*100+a34*10+a35;
ans[n].l4=a41*10000+a42*1000+a43*100+a44*10+a45;
ans[n].l5=a51*10000+a52*1000+a53*100+a54*10+a55;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
int main()
{
freopen("prime3.in","r",stdin);
freopen("prime3.out","w",stdout);
makeprime();
scanf("%d%d",&sum,&a11);
n=0;
for_work();
//printf("%d\n",n);
if (n==0) printf("NONE\n");
else cout_ans();
return 0;
}
【参考程序】：
{
ID: XIONGNA1
PROG: prime3
LANG: PASCAL
}
type r1=record
l1,l2,l3,l4,l5:longint;
end;
var p:array[0..99999] of boolean;
sum,n:longint;
a11,a12,a13,a14,a15,a21,a22,a23,a24,a25,a31,a32,a33,a34,a35,a41:longint;
a42,a43,a44,a45,a51,a52,a53,a54,a55:longint;
ans:array[0..99999] of r1;
procedure makeprime;
var i,j:longint;
begin
fillchar(p,sizeof(p),true);
p[1]:=false;
for i:=2 to 99999 do
if p[i] then
begin
for j:=i to 99999 div i do
p[i*j]:=false;
end;
end;
procedure main;
begin
for a22:=0 to 9 do
for a33:=0 to 9 do
for a44:=0 to 9 do
begin
a55:=sum-a11-a22-a33-a44;
if (a55 in [1,3,7,9]) then
if p[a11*10000+a22*1000+a33*100+a44*10+a55] then
begin
for a51:=1 to 9 do
for a42:=0 to 9 do
for a24:=0 to 9 do
begin
a15:=sum-a51-a42-a33-a24;
if a15 in [1,3,7,9] then
if p[a51*10000+a42*1000+a33*100+a24*10+a15] then
begin
for a12:=1 to 9 do
for a13:=1 to 9 do
begin
a14:=sum-a11-a12-a13-a15;
if a14 in [1..9] then
if p[a11*10000+a12*1000+a13*100+a14*10+a15] then
begin
for a32:=0 to 9 do
begin
a52:=sum-a12-a22-a32-a42;
if a52 in [0..9] then
if p[a12*10000+a22*1000+a32*100+a42*10+a52] then
begin
for a34:=0 to 9 do
begin
a54:=sum-a14-a24-a34-a44;
a53:=sum-a51-a52-a54-a55;
if a54 in [0..9] then
if a53 in [0..9] then
if p[a51*10000+a52*1000+a53*100+a54*10+a55] then
if p[a14*10000+a24*1000+a34*100+a44*10+a54] then
begin
for a21:=1 to 9 do
for a31:=1 to 9 do
begin
a41:=sum-a11-a21-a31-a51;
a35:=sum-a31-a32-a33-a34;
if a41 in [1..9] then
if a35 in [1,3,7,9] then
if p[a31*10000+a32*1000+a33*100+a34*10+a35] then
if p[a11*10000+a21*1000+a31*100+a41*10+a51] then
begin
for a23:=0 to 9 do
begin
a25:=sum-a21-a22-a23-a24;
a43:=sum-a13-a23-a33-a53;
a45:=sum-a41-a42-a43-a44;
if a25 in [1,3,7,9] then
if a43 in [0..9] then
if a45 in [1,3,7,9] then
begin
if p[a21*10000+a22*1000+a23*100+a24*10+a25] then
if p[a41*10000+a42*1000+a43*100+a44*10+a45] then
if p[a13*10000+a23*1000+a33*100+a43*10+a53] then
if p[a15*10000+a25*1000+a35*100+a45*10+a55] then
begin
inc(n);
with ans[n] do
begin
l1:=a11*10000+a12*1000+a13*100+a14*10+a15;
l2:=a21*10000+a22*1000+a23*100+a24*10+a25;
l3:=a31*10000+a32*1000+a33*100+a34*10+a35;
l4:=a41*10000+a42*1000+a43*100+a44*10+a45;
l5:=a51*10000+a52*1000+a53*100+a54*10+a55;
end;
end;
end;
end;
end;
end;
end;
end;
end;
end;
end;
end;
end;
end;
end;
end;
end;
function small(a,b:r1):boolean;
begin
if a.l1<b.l1 then
begin
small:=true; exit;
end;
if a.l1>b.l1 then
begin
small:=false; exit;
end;
if a.l2<b.l2 then
begin
small:=true; exit;
end;
if a.l2>b.l2 then
begin
small:=false; exit;
end;
if a.l3<b.l3 then
begin
small:=true; exit;
end;
if a.l3>b.l3 then
begin
small:=false; exit;
end;
if a.l4<b.l4 then
begin
small:=true; exit;
end;
if a.l4>b.l4 then
begin
small:=false; exit;
end;
if a.l5<b.l5 then
begin
small:=true; exit;
end;
if a.l5>b.l5 then
begin
small:=false; exit;
end;
small:=false;
end;
procedure outans;
var
i,j:longint;
tmp:r1;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if small(ans[j],ans[i]) then
begin
tmp:=ans[j];
ans[j]:=ans[i];
ans[i]:=tmp;
end;
i:=1;
writeln(ans[i].l1);
writeln(ans[i].l2);
writeln(ans[i].l3);
writeln(ans[i].l4);
writeln(ans[i].l5);
for i:=2 to n do
begin
writeln;
writeln(ans[i].l1);
writeln(ans[i].l2);
writeln(ans[i].l3);
writeln(ans[i].l4);
writeln(ans[i].l5);
end;
end;
begin
assign(input,'prime3.in');reset(input);
assign(output,'prime3.out');rewrite(output);
makeprime;
readln(sum,a11);
n:=0;
main;
if n=0 then writeln('NONE')
else outans;
end.