🔗 UVA-10858 Unique Factorization

tags: `回溯(Backtracking)` `DFS`

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

在 ZeroJudge 上只能使用 C++ ，Python 會超時。

題意

在每個測試案例中，會給定一個正整數 $N$ ，請計算 $N$ 的所有唯一因數分解方法數，並列出所有的因數分解。

對於每個輸入的正整數 $N$ ，輸出其唯一的因數分解方法數 $F$ 。如果 $F>0$ ，則接下來的 $F$ 行應包含這些因數分解。每個因數分解中的數字應按非遞減順序排列，並且所有因數分解應按字典順序排列。同一組合視為相同，例如 $12 = 4 \times 3$ 和 $12 = 3 \times 4$ 視為相同。

注意：因數分解中不應包含 $1$ ，且每個因數分解至少包含兩個數。

約束條件

輸入文件中最多包含 $20$ 個測試案例。
$2 \leq N \leq 2 \cdot 10^6$

思路：回溯(Backtracking)

使用回溯的方式來生成所有的因數分解，定義一個回溯函數 $\rm{dfs}(x)$ ，其中 $x$ 是當前待分解的數，並維護一個 $path$ 陣列來存儲當前的因數分解。

每次遞迴時，嘗試將 $x$ $x$ 分解為兩個或多個數的乘積，並確保結果是非遞減的。
- 為了確保結果是非遞減的，我們可以在找尋下一個因數時，限制因數的範圍為 $[pre, x]$ ，其中 $pre$ 是 $path$ 中的最後一個數字，若 $path$ 為空，則 $pre = 2$ 。
若下一個因數 $y$ 能整除 $x$ ，則將 $y$ 加入 $path$ 中，並遞迴處理 $x/y$ 。
當 $x$ 被分解為 $1$ 時，且 $path$ 的長度大於 $1$ 時，將 $path$ 加入答案中。

最後，輸出答案即可。

複雜度分析

時間複雜度： $\mathcal{O}(2^{\sqrt{N}})$ ，取決於 $N$ 的因數分解可能性，由於分數可以兩兩一對，因此最壞情況下有 $2 \cdot 2^{\sqrt{N}}$ 種因數，時間複雜度為 $\mathcal{O}(2^{\sqrt{N}})$ 。
空間複雜度： $\mathcal{O}(2^{\sqrt{N}})$

時間複雜度取決於 $N$ 的因數分解可能性，因此很難估計其複雜度，這裡只是給出一個最壞情況的估計。

ans = []
path = []
def dfs(x):
    if x == 1 and len(path) > 1:
        ans.append(path[:])
        return
    pre = path[-1] if path else 2 # 前一個數字
    for y in range(pre, x+1):
        if x % y == 0:
            path.append(y)
            dfs(x//y)
            path.pop()

while True:
    n = int(input())
    if n == 0:
        break
    ans.clear()
    dfs(n)
    print(len(ans))
    for a in ans:
        print(" ".join(map(str, a)))

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

vector<vector<int>> ans;
vector<int> path;

void dfs(int x) {
    if (x == 1 && path.size() > 1) {
        ans.push_back(path);
        return;
    }
    int pre = path.empty() ? 2 : path.back();
    for (int y = pre; y <= x; y++) {
        if (x % y == 0) {
            path.push_back(y);
            dfs(x / y);
            path.pop_back();
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n;
    while (cin >> n && n) {
        ans.clear();
        dfs(n);
        cout << ans.size() << endl;
        for (auto a : ans)
            for (int i = 0; i < a.size(); i++)
                cout << a[i] << (i == a.size() - 1 ? endl : ' ');
    }
    return 0;
}