UVa 993 - Product of digits

【原题】
For a given non-negative integer number N , find the minimal natural Q such that the product of all digits of Q is equal N .
Input
The first line of input contains one positive integer number, which is the number of data sets. Each subsequent line contains one data set which consists of one non-negative integer number N (0N109) .
Output
For each data set, write one line containing the corresponding natural number Q or `-1' if Q does not exist.
Sample Input
3
1
10
123456789
Sample Output
1
25
-1

【题目大意】
product: 乘积
输入一个非负数N，找到一个最小的自然数Q，使得Q上的每一位数相乘的结果等于N

【分析与总结】
容易想到的是用搜索来做。在搜索之前需要做些剪枝的处理：找到所有能被N整除的数（N的约数），只有这些数才能构成最终答案。
然后就是按照答案Q的长度进行迭代加深搜索，Q的长度从1~10。
有一点需要注意的地方：最高位数不能是1！

【代码】
[cpp]
/*
 * UVa:  993 - Product of digits
 * Result: Accept
 * Time: 0.008s
 * Author: D_Double
 */ 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
using namespace std; 
bool vis[10]; 
int fact[10], nIndex, cur, N; 
int number[10]; 
bool flag; 
 
void dfs(int cur, int sum, int max){ 
    if(cur >= max){ 
        if(sum==N) flag=true; 
        return ; 
    } 
    if(sum > N) return; 
    if(flag) return; 
    for(int i=0; i<nIndex; ++i){ 
        if(cur==0&&i==0&&fact[i]==1) continue;// 注意，最高位不能是1，因为乘1没意义而且使结果大10倍 
        number[cur] = fact[i]; www.2cto.com
        dfs(cur+1, sum*number[cur], max); 
        if(flag) return; 
    } 
} 
 
 
int main(){ 
    int T; 
    scanf("%d",&T); 
    while(T--){ 
        scanf("%d",&N); 
        if(N<10) { 
            printf("%d/n", N); 
            continue; 
        } 
        memset(vis, false, sizeof(vis)); 
        nIndex = 0; 
        for(int i=1; i<=9; ++i) if(N%i==0) 
            fact[nIndex++] = i; 
 
        flag = false; 
        int i; 
        for(i=2; i<=10; ++i){ 
            dfs(0, 1, i); 
            if(flag) break; 
        } 
        if(flag) { 
            for(int j=0; j<i; ++j) printf("%d", number[j]); 
            printf("/n"); 
        } 
        else  
            printf("-1/n"); 
    } 
    return 0; 
} 

 

作者：shuangde800