uva 993 Product of digits (贪心 + 分解因子)

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 (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

题意： 给定一个整数N。。要求出一个最小的Q。。使得Q的每位的乘积等于N。。

思路：贪心。。先把N分解成质因数保存起来。。。然后拿这些质因数去组合。。由于Q要最小。所以先使得位数尽量小。再使得每个位数上的数字尽量小。。就是答案了。。因此我们在组合的时候。要尽量往大了去组合。由于只能组合成一位数。所以从9开始组合。9需要2个3，8需要3个2，6需要2和3。4需要2个2组合。。按9， 8， 6， 4的顺序组合。。最后剩下的数字一定最少。然后在组合后每个数字的个数，按从小到大输出即可。。

..然后看了别人的题解。。。才发现。。其实直接从9开始分解因子就可以了。。我还先分解成质因子了在去组合- - 2B了。没考虑清楚就直接开始写的后果。。还好这题写的还不算太长

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <algorithm>
using namespace std;

int t, n;
int num[10];

int solve() {//质因数去组合。。
    num[9] += num[3] / 2;
    num[3] %= 2;
    num[8] += num[2] / 3;
    num[2] %= 3;
    int sb = min(num[2], num[3]);
    num[6] += sb;
    num[2] -= sb;
    num[3] -= sb;
    num[4] += num[2] / 2;
    num[2] %= 2;
}

int main() {
    scanf("%d", &t);
    while (t --) {
	scanf("%d", &n);
	memset(num, 0, sizeof(num));
	if (n == 0 || n == 1) {//0和1单独出来考虑。
	    printf("%d\n", n);
	    continue;
	}
	for (int i = 2; i <= 7; i ++) {//分解质因数枚举到7就可以了。因为一个位数上的数字必须是一位数。
	    while (n % i == 0 && n != i) {
		num[i] ++;
		n /= i;
	    }
	}
	if (n > 9)
	    printf("-1\n");
	else {
	    num[n] ++;
	    solve();
	    for (int i = 2; i <= 9; i ++) {//按从小到大输出。
		while (num[i]) {
		    printf("%d", i);
		    num[i] --;
		}
	    }
	    printf("\n");
	}
    }
    return 0;
}