HDU 1492：質因數分解求約數個數

問題描述

給定一個只包含質因數 2, 3, 5, 7 的整數 n，求其約數（正因子）的個數。多組測試，n=0 結束。

數學原理：約數個數公式

若 n = p₁^e₁ * p₂^e₂ * ... * pₖ^eₖ（標準質因數分解），則約數個數為：

d(n) = (e₁+1)(e₂+1)...(eₖ+1)

本題已知質因數集合為 {2,3,5,7}，只需分別計算四個質數的指數 a,b,c,d，答案即 (a+1)(b+1)(c+1)(d+1)。

關鍵代碼 (C++)

int main() {
    long long n;
    while (cin >> n && n) {
        int a=0, b=0, c=0, d=0;
        while (n % 2 == 0) { a++; n /= 2; }
        while (n % 3 == 0) { b++; n /= 3; }
        while (n % 5 == 0) { c++; n /= 5; }
        while (n % 7 == 0) { d++; n /= 7; }
        cout << (a+1)*(b+1)*(c+1)*(d+1) << endl;
    }
    return 0;
}

複雜度分析

• 時間：O(log n) — 每次除法至少將 n 縮小一半。
• 空間：O(1)。

關鍵點

• 題目保證 n 只含 2,3,5,7，故分解後 n 必變為 1（可作調試斷言）。
• 使用 long long (或 __int64) 防止溢出。
• 輸入以 0 結束，需處理多組測試。

總結

HDU 1492 是質因數分解求約數個數的直接應用。掌握「指數+1 相乘」公式，並熟練編寫試除法分解代碼，是數論基礎題必備技能。