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
题目大意：给出一个5*5的正方形和左上角的一个数字，要求每一行每一列每一对角线上的数字的和都等于输入的数，并且组成的五位数为质数，输出所有可能的5*5正方形。 算法：这是一道很麻烦的暴力题，朴素的枚举必定会超时，这时候需要调换枚举顺序，以及根据枚举的五位数的位置尽可能排除不可能的情况再枚举，要优化的地方还是比较多的，详见代码。
#include <iostream>
#include <memory.h>
#include <stdio.h>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define MAXN 100000
#define R 0
#define C 1 void output(string str)
{
for(int i=; i<str.length(); i++)
{
printf("%c",str[i]);
if(i%==)
printf("\n");
}
} int getDigSum(int x)
{
int sum=;
while(x!=)
{
sum+=x%;
x/=;
}
return sum;
} bool allDigOdd(int x)
{
while(x!=)
{
int dig=x%;
if(dig%==)
return false;
x/=;
}
return true;
} bool allNoZero(int x)
{
while(x!=)
{
int dig=x%;
if(dig==)
return false;
x/=;
}
return true;
} int isPrime[MAXN+],primeDig[MAXN+][]; int a[][]= {},goalSum=,st;
vector<int> primelist[]; // 以d[ij]表示以i开头，j结尾的字符串
vector<int> primelistMid[]; // 以d[ijk]表示以i开头，j为百位，k结尾的字符串
vector<int> primelistOdd[]; // 各位上的数都为奇数
vector<int> primelistnozero[]; // 各位上都没有0
vector<string> res; int isprime(int type,int num)
{ int sum=;
if(type==R)
{
for(int i=; i<; i++)
sum=sum*+a[num][i];
}
else
{
for(int i=; i<; i++)
sum=sum*+a[i][num];
}
return isPrime[sum];
} void add()
{
string str;
for(int i=; i<; i++)
for(int j=; j<; j++)
{
str+=''+a[i][j];
}
res.push_back(str);
} void initA()
{
for(int i=; i<; i++)
for(int j=; j<; j++)
a[i][j]=;
} int main()
{
freopen("prime3.in","r",stdin);
freopen("prime3.out","w",stdout); initA(); // 求素数表
memset(isPrime,-,sizeof isPrime);
for(int i=; i<=MAXN; i++)
if(isPrime[i])
for(long long j=(long long)i*i; j<=MAXN; j+=i)
isPrime[j]=false; cin>>goalSum>>st; for(int i=; i<MAXN; i++)
if(isPrime[i] && getDigSum(i)!=goalSum)
isPrime[i]=; for(int i=; i<MAXN; i++)
if(isPrime[i])
{
int x=i;
for(int j=; j<; j++)
{
primeDig[i][-j]=x%;
x/=;
}
primelist[i/*+i%].push_back(i);
primelistMid[i/*+(i%)/*+i%].push_back(i);
} // 各位上都为奇数
for(int i=; i<MAXN; i++)
if(isPrime[i] && allDigOdd(i))
primelistOdd[i/*+i%].push_back(i); // 各位上都为非0
for(int i=; i<MAXN; i++)
if(isPrime[i] && allNoZero(i))
primelistnozero[i/*+i%].push_back(i); bool found=false; a[][]=st;
// 枚举 先是右下方数字
for(a[][]=; a[][]<=; a[][]+=)
{
// 枚举左下方数字
for(a[][]=; a[][]<=; a[][]+=)
{
// 枚举右上方数字
for(a[][]=; a[][]<=; a[][]+=)
{
//填充左边质数
for(int i=; i<primelistnozero[st*+a[][]].size(); i++)
{
for(int j=; j<; j++)
a[j][]=primeDig[primelistnozero[st*+a[][]][i]][j]; // 填充上边质数
for(int ii=; ii<primelistnozero[st*+a[][]].size(); ii++)
{
for(int j=; j<; j++)
a[][j]=primeDig[primelistnozero[st*+a[][]][ii]][j]; // 填充下边质数
for(int iii=; iii<primelistOdd[a[][]*+a[][]].size(); iii++)
{
for(int j=; j<; j++)
a[][j]=primeDig[primelistOdd[a[][]*+a[][]][iii]][j]; //填充右边质数
for(int iiii=; iiii<primelistOdd[a[][]*+a[][]].size(); iiii++)
{
for(int j=; j<; j++)
a[j][]=primeDig[primelistOdd[a[][]*+a[][]][iiii]][j]; // 填充中间一点
for(a[][]=; a[][]<=; a[][]++)
{ // 填充主对角线
for(int k=; k<primelistMid[st*+a[][]*+a[][]].size(); k++)
{
a[][]=primeDig[primelistMid[st*+a[][]*+a[][]][k]][];
a[][]=primeDig[primelistMid[st*+a[][]*+a[][]][k]][]; // 填充辅对角线
for(int l=; l<primelistMid[a[][]*+a[][]*+a[][]].size(); l++)
{
a[][]=primeDig[primelistMid[a[][]*+a[][]*+a[][]][l]][];
a[][]=primeDig[primelistMid[a[][]*+a[][]*+a[][]][l]][]; int a12=goalSum-(a[][]+a[][]+a[][]+a[][]);
int a21=goalSum-(a[][]+a[][]+a[][]+a[][]);
int a23=goalSum-(a[][]+a[][]+a[][]+a[][]);
int a32=goalSum-(a[][]+a[][]+a[][]+a[][]);
a[][]=a12;
a[][]=a21;
a[][]=a23;
a[][]=a32;
if(a12>= && a12< && a21>= && a21< && a23>= && a23< && a32>= && a32<
&& isprime(R,) && isprime(R,) && isprime(R,)
&& isprime(C,) && isprime(C,) && isprime(C,))
{
found=true;
add();
}
} }
} }
}
}
}
}
}
} sort(res.begin(),res.end());
bool first=true;
for(int i=; i<res.size(); i++)
{
if(!first)
{
cout<<endl;
}
first=false;
output(res[i]);
} if(!found)
printf("NONE\n");
return ;
}