usaco Prime Cryptarithm 解题报告
题意：
下面是一个乘法竖式，如果用我们给定的那n个数字来取代*，可以使式子成立的话，我们就叫这个式子牛式。
* * * x * * ---------- * * * * * * ---------- * * * *
数字只能取代*，当然第一位不能为0,况且给定的数字里不包括0。
注意一下在美国的学校中教的“部分乘积”，第一部分乘积是第二个数的个位和第一个数的积，第二部分乘积是第二个数的十位和第一个数的乘积.
写一个程序找出所有的牛式。
题解：
枚举符合题意的乘数a和b，然后产生product1，product2，和总的product，分别检查是否符合要求，符合就计数器加一
代码：
/*ID: lishicaoPROG: crypt1LANG: C++*/#include <iostream>#include <fstream>#include <cstring>using namespace std ;ifstream fin ( "crypt1.in" ) ;ofstream fout ( "crypt1.out" ) ;int N , Count = 0 ;int number[10] , num[5] ;void dfs( int ) ;bool check() ;int main(){ fin >> N ; for( int i = 0 ; i < N ; i ++ ) fin >> number[i] ; dfs( 0 ) ; fout << Count << endl ; return 0 ;}void dfs( int depth ){ if( depth == 5 ) { if( check() ){ Count ++ ; } return ; } for( int i = 0 ; i < N ; i ++ ) { num[depth] = number[i] ; dfs( depth + 1 ) ; }}bool check(){ int product1 , product2 , product , temp , flag = 0 ; product1 = num[4] * ( 100 * num[0] + 10 * num[1] + num[2] ) ; product2 = num[3] * ( 100 * num[0] + 10 * num[1] + num[2] ) ; product = product1 + product2 * 10 ; if( product1 >= 1000 || product1 < 100 ) return false ; if( product2 >= 1000 || product2 < 100 ) return false ; if( product >= 10000 || product < 1000 ) return false ; for( int i = 0 ; i < 3 ; i ++ ) { temp = product1 % 10 ; product1 /= 10 ; int flag = 0 ; for( int j = 0 ; j < N ; j ++ ) if( temp == number[j] ) flag = 1 ; if( flag == 0 ) return false ; temp = product2 % 10 ; product2 /= 10 ; flag = 0 ; for( int j = 0 ; j < N ; j ++ ) if( temp == number[j] ) flag = 1 ; if( flag == 0 ) return false ; } for( int i = 0 ; i < 4 ; i ++ ) { temp = product % 10 ; product /= 10 ; int flag = 0 ; for( int j = 0 ; j < N ; j ++ ) if( temp == number[j] ) flag = 1 ; if( flag == 0 ) return false ; } return true ;}