uva 10396——Vampire Numbers

港控/mmm° 2022-08-18 12:28 10阅读 0赞

题意：给定一个n位数（<10），然后求这样的数两个n/2位的数相乘（不能同时被10整除），得到这个n位数的重新组合，然后求这些数。

思路：暴力。直接枚举这样的数，当满足条件的时候放到st的set里面就可以了。

code：

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=1000000;
    const int M=2005;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define cpy(x,a) memcpy(x,a,sizeof(a))
    #define ft(i,s,n) for (int i=s;i<=n;i++)
    #define frt(i,s,n) for (int i=s;i>=n;i--)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    int v[15];
    set<int>st[15];
    set<int>::iterator p;
    int ok(int i,int j){
        int s=i*j;
        cls(v,0);
        while (i){
            v[i%10]++;
            i/=10;
        }
         while (j){
            v[j%10]++;
            j/=10;
        }
         while (s){
            v[s%10]--;
            s/=10;
        }
        ft(i,0,9) if(v[i]) return 0;
        return 1;
    }
    int main()
    {
        int n;
        while (~scanf("%d",&n)){
            int s=1;
            ft(i,1,n/2) s*=10;
            if (st[n].size()==0){
                ft(i,s/10,s){
                    ft(j,i,s){
                        if (i%10==0&&j%10==0) continue;
                        if (ok(i,j)&&(i*j)%2==0) st[n].insert(i*j);
                    }
                }
            }
            for (p=st[n].begin();p!=st[n].end();p++)
                printf("%d\n",*p);
            puts("");
        }
    }