JLOI 2014 聰明的燕姿：約數和與 DFS 枚舉質因子深度解析

問題核心

給定 M(x) 為 x 的約數和，求所有滿足 M(x) = n 的正整數 x。約數和是積性函數，利用質因子分解可轉化為子問題遞歸求解。

數學基礎

設 x = p₁ᵃ¹ × p₂ᵃ² × ... × pₖᵃᵏ，則：

M(x) = ∏(pᵢ⁰ + pᵢ¹ + ... + pᵢᵃⁱ)

每個質因子的貢獻相互獨立，適合 DFS 枚舉。

DFS 狀態設計

dfs(now, pos, rest)：

• now：當前構建的 x 值
• pos：正在枚舉的質因子索引
• rest：剩餘需分解的約數和乘積

剪枝優化

1. 只枚舉 ≤√rest 的質因子
2. 單獨判斷 rest-1 是否為質數，避免重複解
3. 預處理質數表（埃氏篩）加速質因數分解

C++ 關鍵代碼片段

void dfs(ll now, int pos, ll rest) {
    if (rest == 1) { ans[++tot] = now; return; }
    if (pos < primeCnt && isPrime(rest-1)) 
        ans[++tot] = now * (rest-1);
    for (int i = pos; prime[i]*prime[i] <= rest; ++i) {
        ll p = prime[i], sum = p + 1;
        while (sum <= rest) {
            if (rest % sum == 0) dfs(now * p, i+1, rest / sum);
            p *= prime[i];
            sum += p;
        }
    }
}

複雜度與技巧

質數預處理 O(N log log N)，DFS 搜索狀態數較少，實際運行極快。注意 long long 防溢出，答案需排序輸出。