1.3.4 Prime Cryptarithm 牛式
时间： 1ms 内存：64M
描述：
下面是一个乘法竖式，如果用我们给定的那n个数字来取代*，可以使式子成立的话，我们就叫这个式子牛式。
* * * x * * ------- * * * * * * ------- * * * *数字只能取代*，当然第一位不能为0,况且给定的数字里不包括0。
注意一下在美国的学校中教的“部分乘积”，第一部分乘积是第二个数的个位和第一个数的积，第二部分乘积是第二个数的十位和第一个数的乘积.
写一个程序找出所有的牛式。
输入：
Line 1:数字的个数n。 Line 2:N个用空格分开的数字（每个数字都∈ {1,2,3,4,5,6,7,8,9}）。
输出：
共一行，一个数字。表示牛式的总数。下面是样例的那个牛式。 2 2 2 x 2 2 --------- 4 4 4 4 4 4 --------- 4 8 8 4
示例输入：
5
2 3 4 6 8
示例输出：
1
提示：
参考答案（内存最优[752]）：
#include"stdio.h"
int a[10]={0},b[10];
int check(int x)
{
while(x)
{
if(!a[x%10])return 0;
x=x/10;
}
return 1;
}
int main()
{
int n,i,j,k,p,q,sum1,sum,sum2,count;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&b[i]);
a[b[i]]=1;
}
count=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
for(k=0;k<n;k++)
{
for(p=0;p<n;p++)
{
for(q=0;q<n;q++)
{
sum=b[i]*100+b[j]*10+b[k];
sum1=sum*b[p];
sum2=sum*b[q];
if(sum1>999||sum2>999)continue;
if(!check(sum1))continue;
if(!check(sum2)&&sum2<=999)continue;
sum=sum1+sum2*10;
if(sum>9999)continue;
if(!check(sum))continue;
count++;
}
}
}
}
}
printf("%d\n",count);
}参考答案（时间最优[3]）：
#include"stdio.h"
int a[10]={0},b[10];
int check(int x)
{
while(x)
{
if(!a[x%10])return 0;
x=x/10;
}
return 1;
}
int main()
{
int n,i,j,k,p,q,sum1,sum,sum2,count;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&b[i]);
a[b[i]]=1;
}
count=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
for(k=0;k<n;k++)
{
for(p=0;p<n;p++)
{
for(q=0;q<n;q++)
{
sum=b[i]*100+b[j]*10+b[k];
sum1=sum*b[p];
sum2=sum*b[q];
if(sum1>999||sum2>999)continue;
if(!check(sum1))continue;
if(!check(sum2)&&sum2<=999)continue;
sum=sum1+sum2*10;
if(sum>9999)continue;
if(!check(sum))continue;
count++;
}
}
}
}
}
printf("%d\n",count);
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。