| 记录编号 | 214901 | 评测结果 | AAAAAAAAAA | ||
|---|---|---|---|---|---|
| 题目名称 | 素数方阵 | 最终得分 | 100 | ||
| 用户昵称 |  任杰 |
是否通过 | 通过 | ||
| 代码语言 | C++ | 运行时间 | 1.948 s | ||
| 提交时间 | 2015-12-18 19:26:45 | 内存使用 | 9.39 MiB | ||
/*
USER:renjie.1
TASK:prime3
LANG:C++
*/
#include <ctime>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX_L 5
#define MAX_W 7
#define MAX_N 100000
struct TrieNode
{
int cnt;
int v[10];
TrieNode *pNext[10];
} TrieTree,MEM[100000];
struct Mat
{
char seq[31];
};
int cur;
TrieNode *pMat[MAX_W][MAX_W][2];
TrieNode *pDia[MAX_W],*plDia[MAX_W];
int mat[MAX_W][MAX_W];
int PrimeCnt;
int Prime[MAX_N ];
bool NotPrime[MAX_N];
char strNum[30];
Mat res[20000];
int rescnt;
int cnt;
int sum,lefttop;
int first;
bool IsOK();
bool cmp(const Mat &a,const Mat &b)
{
//return strcmp(a.seq,b.seq)<0;
const char *pa,*pb;
pa=a.seq;
pb=b.seq;
while(*pa)
{
if(*pa!=*pb) return *pa<*pb;
pa++;
pb++;
}
return true;
}
inline void MakePrime(long long n)
{
for(long long i=2;i<=n;i++)
{
if(!NotPrime[i])
{
if(i>=10000)
{
Prime[PrimeCnt++]=i;
}
for(long long j=i*i;j<=n;j+=i)
NotPrime[j]=true;
}
}
}
inline void Insert(int num)
{
TrieNode *pNode;
int len=0;
char *pch;
strNum[0]=num/10000+'0';
strNum[1]=num/1000%10+'0';
strNum[2]=num/100%10+'0';
strNum[3]=num/10%10+'0';
strNum[4]=num%10+'0';
pch=strNum;
pNode=&TrieTree;
while(*pch)
{
int id=*pch-'0';
if(!pNode->pNext[id])
{
TrieNode *pNew;
//pNew=new TrieNode();
pNew=&MEM[cur++];
pNode->v[pNode->cnt++]=id;
pNode->pNext[id]=pNew;
}
pNode=pNode->pNext[id];
pch++;
}
}
inline void InitTrieTree()
{
for(int x=0;x<=MAX_L;x++)
{
pMat[0][x][0]=&TrieTree;
pMat[0][x][1]=&TrieTree;
pMat[x][0][0]=&TrieTree;
pMat[x][0][1]=&TrieTree;
}
}
inline TrieNode *GetMinNode(TrieNode *pA,TrieNode *pB)
{
if(pA->cnt<pB->cnt) return pA;
return pB;
}
inline void Cal()
{
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[0][2][0];
pLeft=pMat[1][1][1];
pMin=GetMinNode(pTop,pLeft);
for(int x1=0;x1<pMin->cnt;x1++)//(1,2)
{
int id=pMin->v[x1];
if(pLeft->pNext[id] && pTop->pNext[id])
{
mat[1][2]=id;
pMat[1][2][0]=pTop->pNext[id];
pMat[1][2][1]=pLeft->pNext[id];
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[0][2][0];
pLeft=pMat[1][2][1];
pMin=GetMinNode(pTop,pLeft);
for(int x1=0; x1<pMin->cnt; x1++) //(1,3)
{
int id=pMin->v[x1];
if(pLeft->pNext[id] && pTop->pNext[id])
{
mat[1][3]=id;
pMat[1][3][0]=pTop->pNext[id];
pMat[1][3][1]=pLeft->pNext[id];
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[0][3][0];
pLeft=pMat[1][3][1];
pMin=GetMinNode(pTop,pLeft);
for(int x1=0; x1<pMin->cnt; x1++) //(1,4)
{
int id=pMin->v[x1];
if(pLeft->pNext[id] && pTop->pNext[id])
{
mat[1][4]=id;
pMat[1][4][0]=pTop->pNext[id];
pMat[1][4][1]=pLeft->pNext[id];
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[0][4][0];
pLeft=pMat[1][4][1];
int id=pLeft->v[0];
if(pLeft->pNext[id] && pTop->pNext[id])
{
mat[1][5]=id;
pMat[1][5][0]=pTop->pNext[id];
pMat[1][5][1]=pLeft->pNext[id];
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[1][1][0];
pLeft=pMat[2][0][1];
pMin=GetMinNode(pTop,pLeft);
for(int x1=0; x1<pMin->cnt; x1++)
{
int id=pMin->v[x1];
if(pLeft->pNext[id] && pTop->pNext[id])//(2,1)
{
mat[2][1]=id;
pMat[2][1][0]=pTop->pNext[id];
pMat[2][1][1]=pLeft->pNext[id];
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[2][1][0];
pLeft=pMat[3][0][1];
pMin=GetMinNode(pTop,pLeft);
for(int x1=0; x1<pMin->cnt; x1++)
{
int id=pMin->v[x1];
if(pLeft->pNext[id] && pTop->pNext[id])//(3,1)
{
mat[3][1]=id;
pMat[3][1][0]=pTop->pNext[id];
pMat[3][1][1]=pLeft->pNext[id];
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[3][1][0];
pLeft=pMat[4][0][1];
pMin=GetMinNode(pTop,pLeft);
for(int x1=0; x1<pMin->cnt; x1++)
{
int id=pMin->v[x1];
if(pLeft->pNext[id] && pTop->pNext[id])//(4,1)
{
mat[4][1]=id;
pMat[4][1][0]=pTop->pNext[id];
pMat[4][1][1]=pLeft->pNext[id];
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[4][1][0];
pLeft=pMat[5][0][1];
int id=pTop->v[0];
if(plDia[0]->pNext[id] && pLeft->pNext[id] && pTop->pNext[id])//(5,1)
{
mat[5][1]=id;
pMat[5][1][0]=pTop->pNext[id];
pMat[5][1][1]=pLeft->pNext[id];
plDia[1]=plDia[0]->pNext[id];
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[1][2][0];
pLeft=pMat[2][1][1];
pMin=GetMinNode(pTop,pLeft);
for(int x1=0; x1<pMin->cnt; x1++)
{
int id=pMin->v[x1];
if(pDia[1]->pNext[id] && pTop->pNext[id] && pLeft->pNext[id])//(2,2)
{
mat[2][2]=id;
pMat[2][2][0]=pTop->pNext[id];
pMat[2][2][1]=pLeft->pNext[id];
pDia[2]=pDia[1]->pNext[id];
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[1][3][0];
pLeft=pMat[2][2][1];
pMin=GetMinNode(pTop,pLeft);
for(int x1=0; x1<pMin->cnt; x1++)
{
int id=pMin->v[x1];
if(pTop->pNext[id] && pLeft->pNext[id])//(2,3)
{
mat[2][3]=id;
pMat[2][3][0]=pTop->pNext[id];
pMat[2][3][1]=pLeft->pNext[id];
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[1][4][0];
pLeft=pMat[2][3][1];
pMin=GetMinNode(pTop,pLeft);
for(int x1=0; x1<pMin->cnt; x1++)
{
int id=pMin->v[x1];
if(pTop->pNext[id] && pLeft->pNext[id])//(2,4)
{
mat[2][4]=id;
pMat[2][4][0]=pTop->pNext[id];
pMat[2][4][1]=pLeft->pNext[id];
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[1][5][0];
pLeft=pMat[2][4][1];
int id=pLeft->v[0];
if(pTop->pNext[id] && pLeft->pNext[id])//(2,5)
{
mat[2][5]=id;
pMat[2][5][0]=pTop->pNext[id];
pMat[2][5][1]=pLeft->pNext[id];
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[2][2][0];
pLeft=pMat[3][1][1];
pMin=GetMinNode(pTop,pLeft);
for(int x1=0; x1<pMin->cnt; x1++)
{
int id=pMin->v[x1];
if(pTop->pNext[id] && pLeft->pNext[id])//(3,2)
{
mat[3][2]=id;
pMat[3][2][0]=pTop->pNext[id];
pMat[3][2][1]=pLeft->pNext[id];
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[3][2][0];
pLeft=pMat[4][1][1];
pMin=GetMinNode(pTop,pLeft);
for(int x1=0; x1<pMin->cnt; x1++)
{
int id=pMin->v[x1];
if(plDia[1]->pNext[id] && pTop->pNext[id] && pLeft->pNext[id])//(4,2)
{
mat[4][2]=id;
pMat[4][2][0]=pTop->pNext[id];
pMat[4][2][1]=pLeft->pNext[id];
plDia[2]=plDia[1]->pNext[id];
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[4][2][0];
pLeft=pMat[5][1][1];
int id=pTop->v[0];
if(pTop->pNext[id] && pLeft->pNext[id])//(5,2)
{
mat[5][2]=id;
pMat[5][2][0]=pTop->pNext[id];
pMat[5][2][1]=pLeft->pNext[id];
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[2][3][0];
pLeft=pMat[3][2][1];
pMin=GetMinNode(pTop,pLeft);
for(int x1=0; x1<pMin->cnt; x1++)
{
int id=pMin->v[x1];
if(pDia[2]->pNext[id] && plDia[2]->pNext[id] && pTop->pNext[id] && pLeft->pNext[id])//(3,3)
{
mat[3][3]=id;
pMat[3][3][0]=pTop->pNext[id];
pMat[3][3][1]=pLeft->pNext[id];
pDia[3]=pDia[2]->pNext[id];
TrieNode *pLeft,*pTop,*pMin;
pTop=pMat[2][4][0];
pLeft=pMat[3][3][1];
pMin=GetMinNode(pTop,pLeft);
for(int x1=0; x1<pMin->cnt; x1++)
{
int id=pMin->v[x1];
if(pTop->pNext[id] && pLeft->pNext[id])//(3,4)
{
mat[3][4]=id;
pMat[3][4][0]=pTop->pNext[id];
pMat[3][4][1]=pLeft->pNext[id];
TrieNode *pTop,*pLeft,*pMin;
pTop=pMat[2][5][0];
pLeft=pMat[3][4][1];
int id=pLeft->v[0];
if(pTop->pNext[id] && pLeft->pNext[id])
{
mat[3][5]=id;
pMat[3][5][0]=pTop->pNext[id];
pMat[3][5][1]=pLeft->pNext[id];
TrieNode *pTop,*pLeft,*pMin;
pTop=pMat[3][3][0];
pLeft=pMat[4][2][1];
pMin=GetMinNode(pTop,pLeft);
for(int x1=0; x1<pMin->cnt; x1++)
{
int id=pMin->v[x1];
if(pTop->pNext[id] && pLeft->pNext[id])//(4,3)
{
mat[4][3]=id;
pMat[4][3][0]=pTop->pNext[id];
pMat[4][3][1]=pLeft->pNext[id];
TrieNode *pTop,*pLeft,*pMin;
pTop=pMat[4][3][0];
pLeft=pMat[5][2][1];
pMin=GetMinNode(pTop,pLeft);
int id=pTop->v[0];
if(pTop->pNext[id] && pLeft->pNext[id])//(5,3)
{
mat[5][3]=id;
pMat[5][3][0]=pTop->pNext[id];
pMat[5][3][1]=pLeft->pNext[id];
TrieNode *pTop,*pLeft,*pMin;
pTop=pMat[3][4][0];
pLeft=pMat[4][3][1];
pMin=GetMinNode(pTop,pLeft);
for(int x1=0; x1<pMin->cnt; x1++)
{
int id=pMin->v[x1];
if(pDia[3]->pNext[id] && pTop->pNext[id] && pLeft->pNext[id])//(4,4)
{
mat[4][4]=id;
pMat[4][4][0]=pTop->pNext[id];
pMat[4][4][1]=pLeft->pNext[id];
pDia[4]=pDia[3]->pNext[id];
TrieNode *pTop,*pLeft,*pMin;
pTop=pMat[3][5][0];
pLeft=pMat[4][4][1];
int id=pLeft->v[0];
if(pTop->pNext[id] && pLeft->pNext[id])//(4,5)
{
mat[4][5]=id;
pMat[4][5][0]=pTop->pNext[id];
pMat[4][5][1]=pLeft->pNext[id];
TrieNode *pTop,*pLeft,*pMin;
pTop=pMat[4][4][0];
pLeft=pMat[5][3][1];
int id=pTop->v[0];
if(pTop->pNext[id] && pLeft->pNext[id])//(5,4)
{
mat[5][4]=id;
pMat[5][4][0]=pTop->pNext[id];
pMat[5][4][1]=pLeft->pNext[id];
TrieNode *pTop,*pLeft,*pMin;
pTop=pMat[4][5][0];
pLeft=pMat[5][4][1];
int id=pLeft->v[0];
if(pDia[4]->pNext[id] && pTop->pNext[id] && pLeft->pNext[id])//(5,5)
{
mat[5][5]=id;
if(IsOK())
{
int len=0;
for(int y=1; y<=MAX_L; y++)
{
for(int x=1; x<=MAX_L; x++)
{
res[rescnt].seq[len++]='0'+mat[y][x];
}
res[rescnt].seq[len++]='\n';
}
rescnt++;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
inline bool IsOK()
{
int rsum=0;
int rnum=0;
for(int y=1;y<=MAX_L;y++)
{
rsum+=mat[MAX_L-y+1][y];
rnum=rnum*10+mat[MAX_L-y+1][y];
if(sum<rsum) return false;
}
/*lnum=10000*mat[1][1]+1000*mat[2][2]+100*mat[3][3]+10*mat[4][4]+mat[5][5];
rnum=10000*mat[5][1]+1000*mat[4][2]+100*mat[3][3]+10*mat[2][4]+mat[1][5];
*/
if(NotPrime[rnum]) return false;
/*lsum=mat[1][1]+mat[2][2]+mat[3][3]+mat[4][4]+mat[5][5];
rsum=mat[5][1]+mat[4][2]+mat[3][3]+mat[2][4]+mat[1][5];
*/
if(sum!=rsum) return false;
return true;
}
inline int GetSum(int num)
{
int tsum=0;
while(num)
{
tsum+=num%10;
num/=10;
}
return tsum;
}
int main()
{
freopen("prime3.in","r",stdin);
freopen("prime3.out","w",stdout);
scanf("%d%d",&sum,&first);
MakePrime(99999);
InitTrieTree();
for(int i=0;i<PrimeCnt;i++)
{
if(GetSum(Prime[i])==sum)
{
Insert(Prime[i]);
}
}
mat[1][1]=first;
TrieNode *pTop,*pLeft;
pTop=TrieTree.pNext[first];
pLeft=TrieTree.pNext[first];
pDia[1]=TrieTree.pNext[first];
plDia[0]=&TrieTree;
if(pTop)
{
pMat[1][1][0]=pTop;
pMat[1][1][1]=pLeft;
}
else
{
printf("NONE\n");
return 0;
}
Cal();
if(!rescnt)
{
printf("NONE\n");
return 0;
}
sort(res,res+rescnt,cmp);
for(int i=0;i<rescnt;i++)
{
int len=0;
printf("%s",res[i].seq);
if(i!=rescnt-1)
{
printf("\n");
}
}
}