🔗 UVA-993 Product of digits

tags: `貪婪(Greedy)`

範例程式碼已於UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意

給定一個正整數 $n$ ，輸出一個最小的數字 $$ ，使得 $q$ 的所有位數相乘等於 $n$ 。

思路：貪婪(Greedy)

為使 $q$ 的所有位數相乘等於 $n$ ，需要對 $n$ 做因數分解，並且只能使用 $2$ 到 $9$ 之中的數字。
由於 $q$ 的位數越多，其數值越大，而我們希望 $q$ 的位數越少越好，因此在因數分解時可以先使用較大的數字。舉個例子 $8 = 2^3$ ，但 $8 < 222$ 。
同樣地，為使 $q$ 的值最小，對於因數分解的結果，應該讓較小的數字放在前面，因此可以由小到大檢查因數分解的結果，並加入到答案中。
時間複雜度： $O(\log n)$ ，因數分解。
空間複雜度： $O(1)$ ，因數分解。

T = int(input())

for _ in range(T):
	N = int(input())
	if N <= 1: # 0 or 1
		print(N)
		continue
	# 因數分解，檢查有沒有大於10的因數，注意可以合併2^3=8來縮小答案
	cnt = [0] * 10
	for p in range(9, 1, -1): # [9, 2]
		while (N % p == 0):
			cnt[p] += 1
			N //= p
	if N != 1: # 有大於10的因數
		print(-1)
	else:
		ans = ""
		for p in range(2, 10):
			ans += str(p) * cnt[p]
		print(ans)

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int t, n, cnt[10];
	cin >> t;
	while (t--) {
		cin >> n;
		if (n <= 1) {
			cout << n << endl;
			continue;
		}
		memset(cnt, 0, sizeof(cnt)); 
		for (int p = 9; p > 1; p--) { // 因數分解
			while (n % p == 0) {
				cnt[p]++;
				n /= p;
			}
		}
		if (n != 1) { // 有大於10的因數
			cout << -1 << endl;
		} else {
			string ans = "";
			for (int p = 2; p < 10; p++) {
				while (cnt[p] --) {
					cout << p;
				}
			}
			cout << endl;
		}
	}
	return 0;
}