首页 > 代码库 > Prime Cryptarithm

Prime Cryptarithm

链接

分析:对于三位数我们限定为[100,999],两位数我们限定为[10,99],然后我们依次判断是否满足乘法式且各个数位是否在数列中,若都满足+1

技术分享
 1 /*
 2     PROB:crypt1
 3     ID:wanghan
 4     LANG:C++
 5 */
 6 #include "iostream"
 7 #include "cstdio"
 8 #include "cstring"
 9 #include "string"
10 #include "vector"
11 using namespace std;
12 const int maxn=15;
13 int n;
14 int vis[maxn];
15 int main()
16 {
17     freopen("crypt1.in", "r", stdin);  
18     freopen("crypt1.out", "w", stdout);
19     cin>>n;
20     memset(vis,0,sizeof(vis));
21     for(int i=1;i<=n;i++){
22         int x;
23         cin>>x;
24         vis[x]=1;
25     }
26     int cnt=0;
27     for(int i=100;i<=999;i++){
28         for(int j=10;j<=99;j++){
29             if(i*j>9999)   continue;
30             int num1=i,num2=j;
31             vector<int> n1,n2;
32             int t;
33             while(num1){
34                 t=num1%10;
35                 n1.push_back(t);
36                 num1/=10;
37             }
38             while(num2){
39                 t=num2%10;
40                 n2.push_back(t);
41                 num2/=10;
42             }
43             int flag=0;
44             for(int k=0;k<3;k++){
45                 if(!vis[n1[k]]){
46                     flag=1; break;
47                 }
48             }
49             if(flag)  continue;
50             for(int k=0;k<2;k++){
51                 if(!vis[n2[k]]){
52                     flag=1; break;
53                 }
54             }
55             if(flag)   continue;
56             for(int k=0;k<2;k++){
57                 int yy=0;
58                 for(int z=0;z<3;z++){
59                     int zz=n2[k]*n1[z];
60                     zz+=yy;
61                     if(z==2&&zz>=10){
62                         flag=1; break;
63                     }
64                     int t=zz%10;
65                     yy=zz/10;
66                     if(!vis[t]){
67                         flag=1; break;
68                     }
69                 }
70                 if(flag)  break;
71             }
72             if(flag)   continue;
73             int tt=i*j;
74             while(tt){
75                 int hh=tt%10;
76                 if(!vis[hh]){
77                     flag=1; break;
78                 }
79                 tt/=10;
80             }
81             if(flag)   continue;
82             cnt++;
83         }
84     }
85     cout<<cnt<<endl;
86     return 0;
87 }
View Code

 

Prime Cryptarithm