首页 / 软件开发 / 数据结构与算法 / UVa 993：Product of digits

UVa 993：Product of digits2014-10-31 csdn shuangde800【链接】

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=934

【原题】

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的约数），只有这些数才能构成最终答案。

本栏目更多精彩内容：http://www.bianceng.cn/Programming/sjjg/

然后就是按照答案Q的长度进行迭代加深搜索，Q的长度从1~10。

有一点需要注意的地方：最高位数不能是1！

【代码】

/** 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];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）;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（"
"）;}elseprintf（"-1
"）;}return 0;}