UVA 993 Product of Digits：貪心分解求最小數

UVA 993 Product of Digits：貪心分解求最小數

給定一個正整數 n，要求找出最小的正整數，其各位數字乘積等於 n。若無解則輸出 -1。

核心觀察

• 若 n 無法分解為 2~9 的因子乘積（即分解後剩餘因子 > 9），則無解。
• 為使結果數值最小，應優先分解大因子（9→2），減少位數；最後將得到的因子由小到大排列輸出。

演算法步驟

1. 特判 n = 1，直接輸出 1。
2. 從 9 遞減到 2，盡可能整除 n，將因子存入陣列。
3. 若最終 9，輸出 -1。
4. 否則將收集的因子逆序輸出（即從小到大）。

完整代碼（C++）

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

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        long long n;
        scanf("%lld", &n);
        if (n == 1) {
            printf("1\n");
            continue;
        }
        int ans[50], k = 0;
        for (int i = 9; i >= 2; i--) {
            while (n % i == 0) {
                ans[k++] = i;
                n /= i;
            }
        }
        if (n > 9) {
            printf("-1\n");
            continue;
        }
        for (int i = k - 1; i >= 0; i--)
            printf("%d", ans[i]);
        printf("\n");
    }
    return 0;
}

範例解析

n = 100：

• 分解：100 = 5 × 5 × 4（優先取大因子：100÷5=20, 20÷5=4, 4÷4=1）
• 因子陣列：[5, 5, 4]
• 逆序輸出：455（驗證：4×5×5=100，且為最小）

常見錯誤

• 從小因子開始分解（如 2→9），會導致位數過多，結果不最小。
• 未處理 n = 1 特殊情況。
• 分解後剩餘 n > 9 判斷遺漏。

此題展示了貪心策略在「構造最小數值」問題中的經典應用：大因子優先減少位數，小數字優先排列降低數值。