HDU 2964 Prime Bases：質數基數制轉換解析

HDU 2964 是一道獨特的進制轉換題，使用「質數基數制」：基數依次為 1, 2, 2×3, 2×3×5, 2×3×5×7... 即前 k 個質數的乘積。本文詳細解析算法邏輯與 AC 代碼。

問題描述

給定整數 n，將其表示為：

n = a₀ + a₁×p₀ + a₂×p₀p₁ + a₃×p₀p₁p₂ + ...

其中 p₀=2, p₁=3, p₂=5, p₃=7... 為質數序列。輸出非零項的係數與基數展開式。

核心洞察

1. 基數遞增性：base[k] = base[k-1] × prime[k-1]，嚴格遞增
2. 貪心可行性：從最大不超過 n 的基數開始，係數 a[k] = n / base[k]，餘數繼續分解
3. 係數範圍：0 ≤ a[k] < prime[k]，因若 ≥ prime[k] 則可進位到下一基數
4. 終止條件：餘數為 0 或基數超過 n

算法流程

1. 預計算前 20 個質數及其前綴乘積 base[0..20]
2. 找到最大的 base[rem] ≤ n < base[rem+1]
3. 從 rem 遞減至 0：
     a[i] = n / base[i]
     n   = n % base[i]
4. 輸出非零項：係數 + 基數展開式

完整 AC 代碼

#include 
#include 
using namespace std;

const int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};
long long base[21];
int coeff[21], rem;

void init() {
    base[0] = 1;
    for (int i = 1; i <= 20; i++)
        base[i] = base[i-1] * prime[i-1];
}

void decompose(int n) {
    // 找最大基數位置
    for (rem = 0; rem <= 20; rem++)
        if (base[rem] <= n && base[rem+1] > n) break;

    memset(coeff, 0, sizeof(coeff));
    for (int i = rem; i >= 0; i--) {
        coeff[i] = n / base[i];
        n %= base[i];
    }
}

void output(int n) {
    cout << n << " = ";
    bool first = true;
    for (int i = 0; i <= rem; i++) {
        if (coeff[i] == 0) continue;
        if (!first) cout << " + ";
        first = false;
        cout << coeff[i];
        for (int j = 0; j < i; j++)
            cout << "*" << prime[j];
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();
    int n;
    while (cin >> n && n) {
        decompose(n);
        output(n);
    }
    return 0;
}

關鍵點解析

數學證明補充

質數基數制是一種混合基數制。對於任意正整數 n，存在唯一表示：

n = Σ aᵢ × (Π_{j=0}^{i-1} pⱼ)  ，其中 0 ≤ aᵢ < pᵢ

這與階乘制（基數為 1!, 2!, 3!...）同構。貪心算法的正確性源於：每一步取最大可能係數，餘數必小於當前基數，保證後續位可表示。

測試樣例

Input:
123
100
0

Output:
123 = 1*2*3*5 + 3*2*3 + 1*2 + 1
100 = 1*2*3*5*7 + 2*2*3*5 + 2*2*3 + 2*2 + 2

結語

HDU 2964 考察對混合基數制的理解與貪心分解的實現。關鍵在於識別「質數前綴乘積」作為基數序列，並證明係數範圍受限於下一質數。此類問題在數論、編碼理論、哈希算法中均有應用。