记录编号	78089	评测结果	AAAAAAAAAA
题目名称	素数方阵	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	5.525 s
提交时间	2013-11-03 10:34:05	内存使用	14.62 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<set>
using namespace std;
const int SIZEN=150000;
int isprime[SIZEN]={0};//若为素数则值为true
int digit_sum;
class MAT{
public:
	int s[6][6];
};
bool operator < (MAT a,MAT b){
	int i,j;
	for(i=1;i<=5;i++){
		for(j=1;j<=5;j++){
			if(a.s[i][j]<b.s[i][j]) return true;
			if(a.s[i][j]>b.s[i][j]) return false;
		}
	}
	return false;
}
set<MAT> ans;
class NODE{
public:
	int data;
	int son[10];//加上0~9的10个子节点分别的下标
	bool flag;//子树中是否有素数
	int exs[11];//储存子节点的下标
	int exsnum;
	NODE(){
		flag=false;
		data=0;
		memset(son,0,sizeof(son));
		exsnum=0;
	}
	bool maketree(void);
};
NODE trie[SIZEN];
#define root trie[0]
bool NODE::maketree(void){
	if(data>9999){
		flag=isprime[data];
		son[1]=1;
		return flag;
	}
	int i,sonpos,temp;
	for(i=0;i<=9;i++){
		temp=data*10+i;
		if(temp==data) continue;
		sonpos=temp;
		trie[sonpos].data=temp;
		if(trie[sonpos].maketree()){
			flag=true;
			son[i]=sonpos;
			exs[++exsnum]=i;
		}
	}
	return flag;
}
int getdig(int x){
	int sum=0;
	while(x) sum+=(x%10),x/=10;
	return sum;
}
void getprime(void){
	int i,j;
	int high=(int)sqrt((double)99999);
	for(i=2;i<=high;i++){
		if(!isprime[i]){
			for(j=i*i;j<=99999;j+=i) isprime[j]=true;
		}
	}
	for(i=1;i<10000;i++) isprime[i]=false;
	for(i=10000;i<=99999;i++){
		isprime[i]=!isprime[i];
		if(isprime[i]){
			if(getdig(i)!=digit_sum) isprime[i]=false;
		}
	}
}
int board[6][6]={0};
int decline,decrow;
void print(int board[6][6]){
	int i,j;
	for(i=1;i<=5;i++){
		for(j=1;j<=5;j++) printf("%d ",board[i][j]);
		printf("\n");
	}
	printf("\n");
}
void addmat(void){
	MAT temp;
	int i,j;
	for(i=1;i<=5;i++){
		for(j=1;j<=5;j++) temp.s[i][j]=board[i][j];
	}
	ans.insert(temp);
}
void DFS_line(int x,int y,int z);
void DFS_row(int,int,int);
void check_legal(void){
	int i,x;
	x=0;
	for(i=1;i<=5;i++) x=x*10+board[i][i];
	if(!isprime[x]) return;
	x=0;
	for(i=1;i<=5;i++) x=x*10+board[6-i][i];
	if(!isprime[x]) return;
	addmat();
}
void DFS_line(int x,int k,int nowpos){//第x行,并且前k-1个已先行枚举
	if(x==6) return;
	if(k==6){
		if(x==5) check_legal();
		else{
			int p=0,i;
			for(i=1;i<=x;i++){
				p=trie[p].son[board[i][x]];
			}
			DFS_row(x,x+1,p);
		}
		return;
	}
	int i;
	NODE& now=trie[nowpos];
	int j,temp=0;
	for(j=1;j<x;j++) temp*=10,temp+=board[j][k];
	int v;
	for(i=1;i<=now.exsnum;i++){
		v=now.exs[i];
		if((x==1||k==1)&&v==0) continue;
		if(!trie[temp].son[v]) continue;
		board[x][k]=v;
		DFS_line(x,k+1,now.son[v]);
	}
}
void DFS_row(int x,int k,int nowpos){//第x列,并且前k-1个已先行求出
	if(x==6) return;
	if(k==6){
		int p=0;
		for(int i=1;i<=x;i++){
			p=trie[p].son[board[x+1][i]];
		}
		DFS_line(x+1,x+1,p);
		return;
	}
	int i;
	NODE& now=trie[nowpos];
	int j,temp=0;
	for(j=1;j<x;j++) temp*=10,temp+=board[k][j];
	int v;
	for(i=1;i<=now.exsnum;i++){
		v=now.exs[i];
		if((x==1||k==1)&&v==0) continue;
		if(!trie[temp].son[v]) continue;
		board[k][x]=v;
		DFS_row(x,k+1,now.son[v]);
	}
}
void answer(void){
	set<MAT>::iterator key;
	for(key=ans.begin();key!=ans.end();key++){
		int i,j;
		for(i=1;i<=5;i++){
			for(j=1;j<=5;j++){
				printf("%d",key->s[i][j]);
			}
			printf("\n");
		}
		printf("\n");
	}
}
int main(){
	freopen("prime3.in","r",stdin);
	freopen("prime3.out","w",stdout);
	cin>>digit_sum;
	cin>>board[1][1];
	getprime();
	root.maketree();
	decline=0,decrow=0;
	DFS_line(1,2,root.son[board[1][1]]);
	answer();
	return 0;
}