HDU 2964 Prime Bases：質數基底分解算法詳解

題目大意

給定整數 n，將其分解為特定「質數基底」的線性組合：
n = a0 + a1*p0 + a2*p0*p1 + a3*p0*p1*p2 + ...
其中 p0=2, p1=3, p2=5, p3=7... 為前幾個質數。基底序列為：1, 2, 2×3, 2×3×5, 2×3×5×7...

算法核心洞察

1. 基底遞增性：基底嚴格遞增，超過 n 的基底係數必為 0，無需處理。
2. 模運算性質：對第 k 個基底 B_k，n % B_k 的結果必小於下一個質數 p_k。否則說明應使用更大基底，矛盾。
3. 遞推正確性：從最大基底向下處理，每步取商為係數，餘數傳遞給下一輪，數學歸納法保證正確。

關鍵代碼實現

const int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,39,41,43,47,51,53,57,59};
__int64 a[21];  // 基底陣列：a[0]=1, a[i]=a[i-1]*prime[i-1]
int b[21], rem; // b存係數，rem記錄最大基底位置

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

void deal(int n) {
    // 找到最大基底位置 rem
    for (int i=0; i<=20; i++)
        if (a[i] <= n && a[i+1] > n) { rem = i; break; }
    
    memset(b, 0, sizeof(b));
    for (int i=rem; i>=0; i--) {
        b[i] = n / a[i];  // 係數
        n = n % a[i];     // 餘數傳遞
    }
}

void output(int n) {
    cout << n << " = ";
    for (int i=0; i<=rem; i++)
        if (b[i]) {
            cout << b[i];
            for (int j=0; j