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; 
}