题目描述
给出数位之和S与左上角的数字a，要求填出一个5×5的质数表，使每行每列每条对角线的数都为质数，并且数位之和为给出的数。
思路
当初做这道的时候几经崩溃，根本无法在一个dfs中在规定时限内完成对质数表的填充，无奈之下，我只能多打几个dfs了，具体内容看代码即可。
我们首先肯定要处理处所有数位和为S的质数，这有很多方法，我就不详细讲述了。
我们考虑填数的时候，尽量填已知多的数，这样可以尽早返回能否填充。既然填的是数位，那么我们就需要质数的判断。我的方法是建一个5维的数组。
所以我们先考虑填左上角开始的横、纵、斜三个质数（现在想来可以先填成三角形状，不过我不想改代码了），再开始搜索。
①填这三个质数，我们可以直接搜索开头为a的质数，依次填入。
②我们在尝试填另一条对角线，因为它已知三个数，我们只需依次枚举这两位的数字，判断是否为质数，在进入下一层搜索。
③再同样尝试填第2条横线和第2条纵线。
④试着填第3条横线和第3条纵线。
⑤将剩下填完，记录答案。
代码（极长无比的搜索过程）
#include <bits/stdc++.h> using namespace std; int p[100000],cnt,m[10],s,v; struct aa { char a[6][6]; }g[5000]; bool cmp(aa x,aa y) { for(int i=0;i<5;i++) for(int j=0;j<5;j++) if(x.a[i][j]!=y.a[i][j])return x.a[i][j]<y.a[i][j]; } bool is_prime(int x) { for(int i=2;i<=sqrt(x);i++) if(x%i==0)return 0; return 1; } int sum(int x) { int s=0; while(x) { s+=x%10; x/=10; } return s; } bool f,fhash[10][10][10][10][10],ff[100000]; char ans[10][10]; bool check() { for(int i=0;i<5;i++) { int x=0,ss=0; for(int j=0;j<5;j++) x=x*10+ans[i][j]-'0',ss+=ans[i][j]-'0'; if(ss!=s||!ff[x])return 0; } for(int j=0;j<5;j++) { int x=0,ss=0; for(int i=0;i<5;i++) x=x*10+ans[i][j]-'0',ss+=ans[i][j]-'0'; if(ss!=s||!ff[x])return 0; } return 1; } void dfs7() { int a=ans[0][3]-'0',b=ans[1][3]-'0',c=ans[2][3]-'0',d=ans[3][3]-'0'; for(int i=0;i<10;i++) if(fhash[a][b][c][d][i]) { ans[4][3]=i+'0'; if(check()) { f=1; v++; for(int i=0;i<5;i++) for(int j=0;j<5;j++) g[v].a[i][j]=ans[i][j]; } } } void dfs6() { int a=ans[3][0]-'0',b=ans[3][1]-'0',c=ans[3][2]-'0',d=ans[3][3]-'0'; for(int i=0;i<10;i++) if(fhash[a][b][c][d][i]) { ans[3][4]=i+'0'; dfs7(); } } void dfs5() { int a=ans[0][2]-'0',b=ans[1][2]-'0',c=ans[2][2]-'0'; for(int i=0;i<10;i++) for(int j=0;j<10;j++) if(fhash[a][b][c][i][j]) { ans[3][2]=i+'0';ans[4][2]=j+'0'; dfs6(); } } void dfs4() { int a=ans[2][0]-'0',b=ans[2][1]-'0',c=ans[2][2]-'0'; for(int i=0;i<10;i++) for(int j=0;j<10;j++) if(fhash[a][b][c][i][j]) { ans[2][3]=i+'0';ans[2][4]=j+'0'; dfs5(); } } void dfs3() { int a=ans[0][1]-'0',b=ans[1][1]-'0',c=ans[3][1]-'0'; for(int i=0;i<10;i++) for(int j=0;j<10;j++) if(fhash[a][b][i][c][j]) { ans[2][1]=i+'0';ans[4][1]=j+'0'; dfs4(); } } void dfs2() { int a=ans[1][0]-'0',b=ans[1][1]-'0',c=ans[1][3]-'0'; for(int i=0;i<10;i++) for(int j=0;j<10;j++) if(fhash[a][b][i][c][j]) { ans[1][2]=i+'0';ans[1][4]=j+'0'; dfs3(); } } void dfs1() { int a=ans[4][0]-'0',b=ans[2][2]-'0',c=ans[0][4]-'0'; for(int i=0;i<10;i++) for(int j=0;j<10;j++) if(fhash[a][i][b][j][c]) { ans[3][1]=i+'0';ans[1][3]=j+'0'; dfs2(); } } int main() { // freopen("aa.txt","w",stdout); int x,k=0; scanf("%d%d",&s,&x); for(int i=10000;i<100000;i++) if(is_prime(i)&&sum(i)==s) { p[++k]=i; int a[8]={0},l=i; for(int j=5;j>0;j--) a[j]=l%10,l/=10; fhash[a[1]][a[2]][a[3]][a[4]][a[5]]=1; ff[i]=1; } cnt=k-1; for(int i=1;i<=9;i++) m[i]=lower_bound(p+1,p+cnt+1,i*10000)-p; // printf("%d\n",cnt); // for(int i=1;i<=cnt;i++) // printf("%d\n",p[i]); ans[0][0]=x+'0'; for(int i=m[x];i<m[x+1];i++) for(int j=m[x];j<m[x+1];j++) for(int k=m[x];k<m[x+1];k++) { int l=p[i]; // printf("%d\n",l); for(int q=4;q>0;q--) ans[0][q]=l%10+'0',l/=10; l=p[j]; for(int q=4;q>0;q--) ans[q][0]=l%10+'0',l/=10; l=p[k]; for(int q=4;q>0;q--) ans[q][q]=l%10+'0',l/=10; // printf("%s\n",ans[0]); dfs1(); } if(!f)printf("NONE"); else { sort(g+1,g+v+1,cmp); for(int i=1;i<=v;i++) { for(int j=0;j<5;j++) printf("%s\n",g[i].a[j]); printf("\n"); } } return 0; }