USACOPrime Cryptarithm

http://ace.delos.com/usacoprob2?a=tDp1mPxueqJ&S=crypt1

显而易见，两种解法，一种是直接枚举乘数，共有900*90=81000种可能，然后拆数，判断；另一种是枚举乘数的每一位，边枚举边判断，最坏的情况是9^5=59049种可能，基本上没有超时的可能。。。。

我的是枚举乘数的每一位。

a3 a2 a1 (aa)

* b2 b1 (bb)

-----------------

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;

bool a[10]={0};

bool check(int xx,int minn,int maxx)
{
    if (xx<minn || xx>maxx) return false;
    int temp;
    while (xx>0)
    {
        temp=xx%10;
        if (!a[temp]) return false;
        xx=xx/10;
    }
    return true;
}

int main()
{
    freopen("crypt1.in","r",stdin);
    freopen("crypt1.out","w",stdout);
    int n,x;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        a[x]=true;
    }

    int aa,bb,cc,dd,ee,sum=0;  //一层一个剪枝。。。。
    for (int a1=1;a1<=9;a1++)
    if (a[a1])
        for (int a2=1;a2<=9;a2++)
        if (a[a2])
            for (int a3=1;a3<=9;a3++)
            if (a[a3])
            {
                aa=a3*100+a2*10+a1;
                for (int b1=1;b1<=9;b1++)
                if (a[b1])
                {
                    cc=aa*b1;
                    if (!check(cc,100,1000)) continue;
                    for (int b2=1;b2<=9;b2++)
                    if (a[b2])
                    {
                        dd=aa*b2;
                        if (!check(dd,100,1000)) continue;
                        bb=b2*10+b1;
                        ee=aa*bb;
                        if (check(ee,1000,10000))
                            sum++;
                    }
                }
            }
    cout<<sum<<endl;
    return 0;
}

虽说这题不用剪枝也可以，不过为了让程序更快，并且也更符合人的做法。。。