UVa10396 Vampire Numbers

题目大意

如果一个数为n=x*y,符合以下要求：

1、n为偶数，位数L为4或者6或者8

2、x和y的位数都为L/2

3、x和y两个数字连接在一起，然后进行重排可以得到n

4、x和y两者的尾数不能同时为0

 找出所有满足上述条件的数字。

题解

果断暴力搜索，先进行预先计算（和打表差不多了。。），把n等于4和6以及8的符合的数字计算出来并存储好，我们用set容器来存储，如果用vector容器的话，输出顺序将不是有序的，因此我们选择set容器。刚开始我是用sprintf函数把数字转化成字符串，然后在进行相应的操作的，提交上去的时间异常恐怖啊17.237S。。。然后没用这个函数之后。。时间少了好多。。。只要2.748S。。。sprintf效率也太低了点吧。。。。

#include<iostream>
#include<string.h>
#include<cstdio>
#include<vector>
#include<set>
using namespace std;
set<int>a1,a2,a3;
void Precomputation(int n)
{
    int i,j,k,m,l,r,len,t;
    int f[10],p[10];
    set<int>v;
    if(n==4)
    {
        l=10;
        r=99;
    }
    if(n==6)
    {
        l=100;
        r=999;
    }
    if(n==8)
    {
        l=1000;
        r=9999;
    }
    for(i=l; i<=r; i++)
        for(j=i; j<=r; j++)
        {
            memset(p,0,sizeof(p));
            len=0;
            m=i*j;
            while(m)
            {
                p[m%10]++;
                m/=10;
                len++;
            }
            if(len!=n||(i*j)&1) continue;
            if((i%10==0)&&(j%10==0)) continue;
            memset(f,0,sizeof(f));
            t=i;
            while(t)
            {
                f[t%10]++;
                t/=10;
            }
            t=j;
            while(t)
            {
                f[t%10]++;
                t/=10;
            }
            for(k=0; k<10; k++)
                if(f[k]!=p[k]) break;
            if(k==10)
                v.insert(i*j);
        }
    if(n==4) a1=v;
    else if(n==6) a2=v;
    else
        a3=v;
}
int main(void)
{
    set<int>::iterator iter1,iter2;
    long n;
    Precomputation(4);
    Precomputation(8);
    Precomputation(6);
    while(cin>>n)
    {
        if(n==4)
        {
            iter1=a1.begin();
            iter2=a1.end();
        }
        else if(n==6)
        {
            iter1=a2.begin();
            iter2=a2.end();
        }
        else
        {
            iter1=a3.begin();
            iter2=a3.end();
        }
        while(iter1!=iter2)
        {
            cout<<*iter1<<endl;
            iter1++;
        }
        cout<<endl;
    }
    return 0;
}