UVA 993Product of digits 数目字之积 贪心水题

UVA 993Product of digits 数字之积 贪心水题

题意：求出一个数，各个位数上相乘的积等于所给的数。

枚举2-9,如果找到一个数能整除那个数就枚举下一位，递归即可。

代码：

 /*
 *   Author:        illuz <iilluzen[at]gmail.com>
 *   Blog:          http://blog.****.net/hcbbt
 *   File:          uva993.cpp
 *   Lauguage:      C/C++
 *   Create Date:   2013-09-01 00:24:29
 *   Descripton:    uva993, brute 
 */
#include <cstdio>
#define rep(i, n) for (int i = 0; i < (n); i++)

const int MAXN = 100;
bool flag;
int t, n, a[20], cnt;

void solve(int d) {
	if (flag) return;
	if (!n) return;
	n /= 10;
	for (int i = 9; i >= 2 && !flag; i--) {
		if (d % i == 0) {
			solve(d / i);
			a[cnt++] = i;
			return;
		}
	}
	flag = true;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		if (n == 1) {
			printf("1\n");
			continue;
		}
		if (n == 0) {
			printf("0\n");
			continue;
		}
		flag = false;
		cnt = 0;
		solve(n);
		if (!flag) rep(i, cnt) printf("%d", a[i]);
		else printf("-1");
		printf("\n");
	}
	return 0;
}