UVa 993: Product of digits

本文主要是介绍UVa 993: Product of digits，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题很简单。先将N用2,3,5,7（即10以内的素数）分解因数（需要先特殊判断N不为1），然后将可以合并的因数合并（如2*2合并成4，）这样求得的结果位数会减少，大小肯定会小一些。具体实现见代码。

我的解题代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <algorithm>
using namespace std;int c[12];
int T;
int N;int main()
{cin >> T;while(T--){cin >> N;if(N==1) { cout << 1 << endl; continue; }memset(c,0,sizeof(c));while(N!=1)	//分解N{		if(N%2==0) { c[2]++; N/=2; }else if(N%3==0) { c[3]++; N/=3; }else if(N%5==0) { c[5]++; N/=5; }else if(N%7==0) { c[7]++; N/=7; }else break;}if(N!=1) { cout << -1 << endl; continue; }while(1)	//合并N的因子{if(c[2]>=3) { c[2]-=3; c[8]++; }	//因子有三个2，合并为8else if(c[2]>=2) { c[2]-=2; c[4]++; }	//有两个2，合并为4else if(c[3]>=2) { c[3]-=2; c[9]++; }	//有两个3，合并为9else if(c[2]>=1 && c[3]>=1) { c[2]--; c[3]--; c[6]++; }	//有一个2和一个3，合并为6else break;}for(int i=2; i<=9; i++){//输出结果while(c[i]){cout << i;c[i]--;}}cout << endl;}return 0;
}

附上题目如下：

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 (0N10⁹) .

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

这篇关于UVa 993: Product of digits的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---