题目描述

给定一个如下乘法算式：

      * * *
   x    * *
    -------
      * * *         
    * * *           
    -------
    * * * *

现在，给定 N 个 1∼9 之间的数字，请你在这些数字中选取合适的数字填入算式，代替 * 号，使得算式成立。

所给的数字可以在算式中出现多次。

算式中不能出现没有给出的数字。

请问，共有多少种不同的填法？

输入格式
第一行包含整数 N。

第二行包含 N 个整数，表示给定的数字，数据保证这 N 个数字互不相同。

输出格式
输出一个整数，表示可以使得算式成立的总填法数量。

数据范围
1≤N≤9

样例

输入样例：
5
2 3 4 6 8
输出样例：
1
样例解释
唯一的使得算式成立的填法如下：

      2 2 2
    x   2 2
     ------
      4 4 4
    4 4 4
  ---------
    4 8 8 4
每个代替 * 号的数字均在给出数字之中，满足条件。

再看一组不满足条件的填法：

      2 2 2   <-- OK:  三个数字均在 {2, 3, 4, 6, 8} 之中
    x   2 3   <-- OK:  两个数字均在 {2, 3, 4, 6, 8} 之中
     ------
      6 6 6   <-- OK:  三个数字均在 {2, 3, 4, 6, 8} 之中
    4 4 4     <-- OK:  三个数字均在 {2, 3, 4, 6, 8} 之中
  ---------
    5 1 0 6   <-- NOT OK: 5,1,0 均不在 {2, 3, 4, 6, 8} 之中

算法1

(暴力枚举)

这个题目也是暴力，我们枚举所有的3位数和2位数的乘积，然后依次判断，第一个数是不是一个三位数，第二个数是不是一个三位数，结果是不是一个四位数，因为需要枚举两个因子和三个积中的所有数是否都出现过，这个时候我们可以用一个数组来保存所有的数，然后循环处理一遍就可以了

C++ 代码

#include<bits/stdc++.h>
using namespace std;
bool st[10];
int t[10];
bool f()
{
    for(int i=0;i<5;i++)//依次判断每个数 
    {
        int a=t[i]; 
        while(a) 
        {
            if(st[a%10]==false)//某个数字没有出现 
            return false;
            a/=10;
        }
    }
    return 1;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        st[x]=1;
    }
    int cnt=0;
    for(int i=100;i<=999;i++)
        for(int j=10;j<=99;j++)
        {
            int a=i*(j%10),b=i*(j/10),c=i*j;
            if(a>=100&&a<=999&&b>=100&b<=999&&c>=1000&&b<=9999)//a是3位数，b是3位数，c是4位数 
            {
                t[0]=i,t[1]=j,t[2]=a,t[3]=b,t[4]=c;//5个数依次赋值 
                if(f()) //每个数字都出现过 
                    cnt++;
            }
        }
    cout<<cnt<<endl;
    return 0;
}