题目描述

给定一个非负整数NNN，要求找到一个最小的自然数QQQ，使得QQQ的各位数字之积恰好等于NNN。若不存在这样的QQQ，则输出−1-1−1。对于N=0N = 0N=0和N=1N = 1N=1的情况，答案分别为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，因此对于N>0N > 0N>0的情况，QQQ的每一位数字必须取自111到999。为了使QQQ最小，需要满足两个条件：第一，QQQ的位数尽可能少；第二，在位数相同的情况下，高位数字尽可能小。由于乘积固定为NNN，将NNN分解为若干位数字的乘积时，应优先使用较大的数字（如999、888等），因为大数字能更快地减少NNN的因子，从而减少位数。当NNN无法被222到999中的任何数字整除且N>1N > 1N>1时，说明NNN含有大于999的质因子，此时不存在满足条件的QQQ，应输出−1-1−1。对于N=0N = 0N=0和N=1N = 1N=1，直接输出000和111即可。

解题思路

对于每个输入NNN，首先处理特殊情况：若N=0N = 0N=0或N=1N = 1N=1，直接输出NNN。对于N>1N > 1N>1，从数字999到222依次尝试整除NNN。若NNN能被某个数字iii整除，则将iii添加到结果数字的最前面，并令N=N/iN = N / iN=N/i，然后重新从999开始尝试。重复此过程直到N=1N = 1N=1或无法再被任何数字整除。若最终N>1N > 1N>1，说明原数含有大于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//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases,n;cin>>cases;for(intc=1;c<=cases;c++){cin>>n;if(n==0||n==1){cout<<n<<'\n';continue;}string digits;while(n>1){boolupdated=false;for(inti=9;i>=2;i--)if(n%i==0){digits.insert(digits.begin(),'0'+i);n/=i;updated=true;break;}if(!updated)break;}if(n>1)cout<<"-1\n";elsecout<<digits<<'\n';}return0;}

总结

本题的关键在于贪心策略：从999到222依次分解NNN，优先使用较大数字以减少结果位数，并保证高位数字尽可能小。同时需要注意N=0N = 0N=0和N=1N = 1N=1的特殊情况，以及当NNN含有大于999的质因子时输出−1-1−1。掌握数字分解与贪心构造的方法，有助于解决类似的数字构造问题。