题目描述给定一个非负整数NNN要求找到一个最小的自然数QQQ使得QQQ的各位数字之积恰好等于NNN。若不存在这样的QQQ则输出−1-1−1。对于N0N 0N0和N1N 1N1的情况答案分别为000和111。输入格式输入的第一行包含一个正整数表示数据集的个数。接下来的每一行包含一个数据集即一个非负整数NNN满足0≤N≤1090 \le N \le 10^90≤N≤109。输出格式对于每个数据集输出一行包含对应的自然数QQQ若QQQ不存在则输出−1-1−1。样例输入3 1 10 123456789样例输出1 25 -1题目分析该问题要求构造一个最小的自然数QQQ使其各位数字的乘积等于给定的NNN。由于QQQ的每一位数字只能是000到999而000会使乘积变为000因此对于N0N 0N0的情况QQQ的每一位数字必须取自111到999。为了使QQQ最小需要满足两个条件第一QQQ的位数尽可能少第二在位数相同的情况下高位数字尽可能小。由于乘积固定为NNN将NNN分解为若干位数字的乘积时应优先使用较大的数字如999、888等因为大数字能更快地减少NNN的因子从而减少位数。当NNN无法被222到999中的任何数字整除且N1N 1N1时说明NNN含有大于999的质因子此时不存在满足条件的QQQ应输出−1-1−1。对于N0N 0N0和N1N 1N1直接输出000和111即可。解题思路对于每个输入NNN首先处理特殊情况若N0N 0N0或N1N 1N1直接输出NNN。对于N1N 1N1从数字999到222依次尝试整除NNN。若NNN能被某个数字iii整除则将iii添加到结果数字的最前面并令NN/iN N / iNN/i然后重新从999开始尝试。重复此过程直到N1N 1N1或无法再被任何数字整除。若最终N1N 1N1说明原数含有大于999的质因子输出−1-1−1否则输出构造出的数字字符串。由于每次选择尽可能大的数字得到的数字位数最少且因为每次将新数字插入到最前面最终得到的数字字符串即为满足条件的最小自然数。时间复杂度为O(log⁡N)O(\log N)O(logN)空间复杂度为O(log⁡N)O(\log N)O(logN)。代码实现// Product of digits// UVa ID: 993// Verdict: Accepted// Submission Date: 2016-01-09// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases,n;cincases;for(intc1;ccases;c){cinn;if(n0||n1){coutn\n;continue;}string digits;while(n1){boolupdatedfalse;for(inti9;i2;i--)if(n%i0){digits.insert(digits.begin(),0i);n/i;updatedtrue;break;}if(!updated)break;}if(n1)cout-1\n;elsecoutdigits\n;}return0;}总结本题的关键在于贪心策略从999到222依次分解NNN优先使用较大数字以减少结果位数并保证高位数字尽可能小。同时需要注意N0N 0N0和N1N 1N1的特殊情况以及当NNN含有大于999的质因子时输出−1-1−1。掌握数字分解与贪心构造的方法有助于解决类似的数字构造问题。