UVA - 993 - Product of digits （容易贪心）

UVA - 993 - Product of digits （简单贪心）

993 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 (0 ≤ N ≤109).

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的9 ~ 2的因数（按降序找）的个数，输出按升序

AC代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

int T, N;
int a[10];

int main() {
	scanf("%d", &T);
	while(T--) {
		scanf("%d", &N);
		if(N == 1) {
			printf("1\n");
			continue;
		}
		memset(a, 0, sizeof(a));
		for(int i = 9; i >= 2; i--) {
			if(N == 1) break;
			while(N % i == 0) {
				a[i] ++;
				N /= i;
			}
		}
		if(N != 1) {
			printf("-1\n");
			continue;
		}
		for(int i = 2; i < 10; i++) {
			while(a[i] != 0) {
				printf("%d", i);
				a[i] --;
			}
		}
		printf("\n");
	}
	return 0;
}