题目描述

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

该乘法竖式是一个三位数×两位数得到一个四位数，中间两次乘法得到的都是一个三位数。

数字只能取代 *，当然第一位不能为 0，况且给定的数字里不包括 0。

注意一下学校中教的“部分乘积”，第一部分乘积是第二个数的个位和第一个数的积，第二部分乘积是第二个数的十位和第一个数的乘积。

请计算出牛式的数量。

输入格式

第一行一个正整数 n，表示可用的数有n个。 第二行 n 个正整数 a i，表示可用的数。

输出格式

输出一行一个整数，表示牛式的总数。

样例输入

5
2 3 4 6 8

样例输出

1

提示

对于 100% 的数据，1≤n≤9，ai都是1~9范围内的整数且不重复。

满足样例的一个式子为222*22=4884

样例代码_

#include<bits/stdc++.h>
using namespace std;
int n, v[10], x, k, p, q, ans;
bool check(int x) { // 判断每个数位是不是都由要求的数构成 
	while (x > 0) {
		if (v[x%10] == 0) return false;
		x /= 10;
	} 
	return true;
} 

int main() {
	scanf("%d", &n);
	for (int i=1; i<=9; i++) {
		v[i] = 0;
	}
	for (int i=1; i<=n; i++) {
		scanf("%d", &x);
		v[x] = 1; // 标记可以使用的数字 
	} 
	ans = 0;
	for (int i=100; i<=999; i++) {
		for (int j=10; j<=99; j++) {
			k = i * j;  // 最终乘积 
			p = j%10 * i; // 中间计算出的第一个乘积 
			q = j/10 * i; // 中间计算出的第二个乘积 
			if (k > 9999 || p > 999 || q > 999) continue; 
			// 中间计算出的两个乘积不能是四位数，最终乘积不能是五位数
			if (check(i) && check(j) && check(k) && check(p) && check(q)) {
				ans ++;
			} 
		}
	} 
	printf("%d", ans);
	return 0;
}