首页 > 代码库 > USACO6.4-The Primes
USACO6.4-The Primes
IOI‘94
In the square below, each row, each column and the two diagonals canbe read as a five digit prime number. The rows are read from left toright. The columns are read from top to bottom. Both diagonals areread 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.
113511403330323532011331311351332033032314033333111331313043323035023113331
题目大意：给出一个5*5的正方形和左上角的一个数字，要求每一行每一列每一对角线上的数字的和都等于输入的数，并且组成的五位数为质数，输出所有可能的5*5正方形。
算法：这是一道很麻烦的暴力题，朴素的枚举必定会超时，这时候需要调换枚举顺序，以及根据枚举的五位数的位置尽可能排除不可能的情况再枚举，要优化的地方还是比较多的，详见代码。
1 #include <iostream> 2 #include <memory.h> 3 #include <stdio.h> 4 #include <vector> 5 #include <string> 6 #include <algorithm> 7 using namespace std; 8 #define MAXN 100000 9 #define R 0 10 #define C 1 11 12 13 void output(string str) 14 { 15 for(int i=0; i<str.length(); i++) 16 { 17 printf("%c",str[i]); 18 if(i%5==4) 19 printf("\n"); 20 } 21 } 22 23 int getDigSum(int x) 24 { 25 int sum=0; 26 while(x!=0) 27 { 28 sum+=x%10; 29 x/=10; 30 } 31 return sum; 32 } 33 34 bool allDigOdd(int x) 35 { 36 while(x!=0) 37 { 38 int dig=x%10; 39 if(dig%2==0) 40 return false; 41 x/=10; 42 } 43 return true; 44 } 45 46 bool allNoZero(int x) 47 { 48 while(x!=0) 49 { 50 int dig=x%10; 51 if(dig==0) 52 return false; 53 x/=10; 54 } 55 return true; 56 } 57 58 int isPrime[MAXN+10],primeDig[MAXN+10][5]; 59 60 int a[5][5]= {0},goalSum=0,st; 61 vector<int> primelist[100]; // 以d[ij]表示以i开头，j结尾的字符串 62 vector<int> primelistMid[1000]; // 以d[ijk]表示以i开头，j为百位，k结尾的字符串 63 vector<int> primelistOdd[100]; // 各位上的数都为奇数 64 vector<int> primelistnozero[100]; // 各位上都没有0 65 vector<string> res; 66 67 int isprime(int type,int num) 68 { 69 70 int sum=0; 71 if(type==R) 72 { 73 for(int i=0; i<5; i++) 74 sum=sum*10+a[num][i]; 75 } 76 else 77 { 78 for(int i=0; i<5; i++) 79 sum=sum*10+a[i][num]; 80 } 81 return isPrime[sum]; 82 } 83 84 void add() 85 { 86 string str; 87 for(int i=0; i<5; i++) 88 for(int j=0; j<5; j++) 89 { 90 str+=‘0‘+a[i][j]; 91 } 92 res.push_back(str); 93 } 94 95 void initA() 96 { 97 for(int i=0; i<5; i++) 98 for(int j=0; j<5; j++) 99 a[i][j]=100;100 }101 102 int main()103 {104 freopen("prime3.in","r",stdin);105 freopen("prime3.out","w",stdout);106 107 initA();108 109 // 求素数表110 memset(isPrime,-1,sizeof isPrime);111 for(int i=2; i<=MAXN; i++)112 if(isPrime[i])113 for(long long j=(long long)i*i; j<=MAXN; j+=i)114 isPrime[j]=false;115 116 117 cin>>goalSum>>st;118 119 for(int i=10000; i<MAXN; i++)120 if(isPrime[i] && getDigSum(i)!=goalSum)121 isPrime[i]=0;122 123 for(int i=10000; i<MAXN; i++)124 if(isPrime[i])125 {126 int x=i;127 for(int j=0; j<5; j++)128 {129 primeDig[i][4-j]=x%10;130 x/=10;131 }132 primelist[i/10000*10+i%10].push_back(i);133 primelistMid[i/10000*100+(i%1000)/100*10+i%10].push_back(i);134 }135 136 // 各位上都为奇数137 for(int i=10000; i<MAXN; i++)138 if(isPrime[i] && allDigOdd(i))139 primelistOdd[i/10000*10+i%10].push_back(i);140 141 // 各位上都为非0142 for(int i=10000; i<MAXN; i++)143 if(isPrime[i] && allNoZero(i))144 primelistnozero[i/10000*10+i%10].push_back(i);145 146 bool found=false;147 148 a[0][0]=st;149 // 枚举 先是右下方数字150 for(a[4][4]=1; a[4][4]<=9; a[4][4]+=2)151 {152 // 枚举左下方数字153 for(a[4][0]=1; a[4][0]<=9; a[4][0]+=2)154 {155 // 枚举右上方数字156 for(a[0][4]=1; a[0][4]<=9; a[0][4]+=2)157 {158 //填充左边质数159 for(int i=0; i<primelistnozero[st*10+a[4][0]].size(); i++)160 {161 for(int j=0; j<5; j++)162 a[j][0]=primeDig[primelistnozero[st*10+a[4][0]][i]][j];163 164 // 填充上边质数165 for(int ii=0; ii<primelistnozero[st*10+a[0][4]].size(); ii++)166 {167 for(int j=0; j<5; j++)168 a[0][j]=primeDig[primelistnozero[st*10+a[0][4]][ii]][j];169 170 171 // 填充下边质数172 for(int iii=0; iii<primelistOdd[a[4][0]*10+a[4][4]].size(); iii++)173 {174 for(int j=0; j<5; j++)175 a[4][j]=primeDig[primelistOdd[a[4][0]*10+a[4][4]][iii]][j];176 177 178 //填充右边质数179 for(int iiii=0; iiii<primelistOdd[a[0][4]*10+a[4][4]].size(); iiii++)180 {181 for(int j=0; j<5; j++)182 a[j][4]=primeDig[primelistOdd[a[0][4]*10+a[4][4]][iiii]][j];183 184 185 // 填充中间一点186 for(a[2][2]=0; a[2][2]<=9; a[2][2]++)187 {188 189 // 填充主对角线190 for(int k=0; k<primelistMid[st*100+a[2][2]*10+a[4][4]].size(); k++)191 {192 a[1][1]=primeDig[primelistMid[st*100+a[2][2]*10+a[4][4]][k]][1];193 a[3][3]=primeDig[primelistMid[st*100+a[2][2]*10+a[4][4]][k]][3];194 195 // 填充辅对角线196 for(int l=0; l<primelistMid[a[4][0]*100+a[2][2]*10+a[0][4]].size(); l++)197 {198 a[3][1]=primeDig[primelistMid[a[4][0]*100+a[2][2]*10+a[0][4]][l]][1];199 a[1][3]=primeDig[primelistMid[a[4][0]*100+a[2][2]*10+a[0][4]][l]][3];200 201 int a12=goalSum-(a[1][0]+a[1][1]+a[1][3]+a[1][4]);202 int a21=goalSum-(a[0][1]+a[1][1]+a[3][1]+a[4][1]);203 int a23=goalSum-(a[0][3]+a[1][3]+a[3][3]+a[4][3]);204 int a32=goalSum-(a[3][0]+a[3][1]+a[3][3]+a[3][4]);205 a[1][2]=a12;206 a[2][1]=a21;207 a[2][3]=a23;208 a[3][2]=a32;209 if(a12>=0 && a12<10 && a21>=0 && a21<10 && a23>=0 && a23<10 && a32>=0 && a32<10210 && isprime(R,1) && isprime(R,2) && isprime(R,3)211 && isprime(C,1) && isprime(C,2) && isprime(C,3))212 {213 found=true;214 add();215 }216 }217 218 }219 }220 221 }222 }223 }224 }225 }226 }227 }228 229 sort(res.begin(),res.end());230 bool first=true;231 for(int i=0; i<res.size(); i++)232 {233 if(!first)234 {235 cout<<endl;236 }237 first=false;238 output(res[i]);239 }240 241 if(!found)242 printf("NONE\n");243 return 0;244 }
USACO6.4-The Primes
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。