HDU 4937 Lucky Number：因數枚舉法求合法進制底數

題目回顧

同 HDU 4937（ID 208915），本文採用因數枚舉而非分位數討論。核心觀察：若 n 在底數 b 下各位均在 {3,4,5,6}，則 n = a₀ + a₁b + a₂b² + ...，其中每個 aᵢ ∈ {3,4,5,6}。對於固定的末位 a₀ ∈ {3,4,5,6}，有 n - a₀ = b · (a₁ + a₂b + ...)，故 b 必須是 n - a₀ 的因數。

算法流程

1. 特判 n ∈ {3,4,5,6} → 輸出 -1。
2. 對每個 a₀ ∈ {3,4,5,6}，設 m = n - a₀。若 m ≤ 0 跳過。
3. 對 m 進行質因子分解，再 DFS 生成所有因數 b。
4. 對每個因數 b，檢查 n 在底數 b 下是否全為 {3,4,5,6}。合法則加入集合。
5. 輸出集合大小。

關鍵代碼

= 3 && n <= 6) { printf("Case #%d: -1\n", cas++); continue; }
        ans.clear();
        for (ll a0 = 3; a0 <= 6; a0++) {
            if (n > a0) {
                factorize(n - a0);
                dfs(0, 1);
            }
        }
        printf("Case #%d: %d\n", cas++, (int)ans.size());
    }
}

兩種方法對比

優化建議

• 質因子分解上界 √m ≤ 1e6，預篩 1e6 內質數即可。
• DFS 生成因數時可剪枝：若當前乘積已超過 n 則停止（但因數 ≤ m < n，通常不需要）。
• 使用 set 自動去重，最終答案為 ans.size()。