1012. 【USACO题库】1.3.4 Prime Cryptarithm牛式

题目描述

下面是一个乘法竖式，如果用我们给定的那几个数字来取代*，可以使式子成立的话，我们就叫这个式子牛式。
* * *
x * *
-------
* * *
* * *
-------
* * * *

数字只能取代*，当然第一位不能为0。写一个程序找出所有的牛式。

输入

从文件 crypt1.in 中读入数据。

Line 1:数字的个数。
Line 2:N个用空格分开的数字（每个数字都∈{1,2,3,4,5,6,7,8,9}） 。

输出

输出到文件 crypt1.out 中。

共一行，一个数字。表示牛式的总数。

样例输入 复制

5
2 3 4 6 8

样例输出 复制

1

提示

上述样例只有以下情况成立：
2 2 2
x 2 2
------
4 4 4
4 4 4
---------
4 8 8 4

#include <stdio.h>
#include <time.h>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int arr[100]= {0},n;
/*
7
4 1 2 5 6 7 3

*/
bool check(int n,int d)
{
	while(n)
	{
		if(n%10==d) return true;
		n/=10;
	}
	return false;
}
bool solve(int val)
{
	while(val)
	{
		int p=val%10,f=0;
		
		for(int i=1;i<=n;i++)
		{
			if(arr[i] == p) {
				//出现了
				f=1;break; 
			}
		}
		if(!f) return false;
		val/=10;
	}
	return true;
}
int main()
{
	//freopen("crypt1.in","r",stdin);
	//freopen("crypt1.out","w",stdout);
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	{
		scanf("%d",&arr[i]);
	}

	int ans=0;
	for(int i=1; i<=n; i++)
	{
		if(arr[i] == 0) continue;
		for(int j=1; j<=n; j++)
		{
			for(int k=1; k<=n; k++)
			{
				for(int l=1; l<=n; l++)
				{
					if(arr[l] == 0) continue;
					for(int p=1; p<=n; p++)
					{
						int c1=arr[i]*100+arr[j]*10+arr[k];
						int c2=arr[l]*10+arr[p];
						int c3=arr[p]*c1;
						int c4=arr[l]*c1; //注意!还要放大10x
						int c5=c1*c2;
						if(c5==c3+c4*10 && c5<=9999 && c3<=999 && c4<=999 && c4>=100 && solve(c3) && solve(c4) && solve(c5))
						{
							//printf("c1=%d c2=%d c3=%d c4=%d c5=%d\n",c1,c2,c3,c4,c5);
							ans++; 
						}
					}
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}