HDU 1452 Happy 2004：數論與除數函數的模運算技巧

HDU 1452 要求計算 S(2004^n) mod 29，其中 S(k) 為 k 的所有正因子之和（除數函數 σ₁(k)）。

數學基礎：除數函數性質

對於 n = p₁^a₁ p₂^a₂ ... pₖ^aₖ，除數函數具有積性：

σ₁(n) = σ₁(p₁^a₁) × σ₁(p₂^a₂) × ... × σ₁(pₖ^aₖ)
σ₁(p^a) = 1 + p + p² + ... + p^a = (p^(a+1) - 1) / (p - 1)

題目具體分解

2004 = 2² × 3 × 167

2004^n = 2^(2n) × 3^n × 167^n

利用積性：

S(2004^n) = S(2^(2n)) × S(3^n) × S(167^n)
          = [(2^(2n+1)-1)/(2-1)] × [(3^(n+1)-1)/(3-1)] × [(167^(n+1)-1)/(167-1)]
          = (2^(2n+1)-1) × (3^(n+1)-1)/2 × (167^(n+1)-1)/166

模 29 運算處理除法

模算術中除法轉換為乘以模逆元：

a / b ≡ a × b⁻¹ (mod m)，其中 b⁻¹ 滿足 b × b⁻¹ ≡ 1 (mod m)

模 29 下：
2⁻¹ ≡ 15  (因 2×15=30≡1)
166⁻¹ ≡ 18 (因 166≡166-5×29=21, 21×18=378≡1 mod 29)

最終公式

ans = (2^(2n+1)-1) × 1
    × (3^(n+1)-1) × 15
    × (167^(n+1)-1) × 18
    (mod 29)

快速冪模運算

long long mod_pow(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

完整 AC 代碼

#include <bits/stdc++.h>
using namespace std;
const int MOD = 29;

long long mod_pow(long long a, long long b) {
    long long res = 1;
    a %= MOD;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    long long n;
    while (cin >> n && n) {
        long long term1 = (mod_pow(2, 2*n + 1) - 1 + MOD) % MOD;
        long long term2 = (mod_pow(3, n + 1) - 1 + MOD) % MOD * 15 % MOD;
        long long term3 = (mod_pow(167, n + 1) - 1 + MOD) % MOD * 18 % MOD;
        
        long long ans = term1 * term2 % MOD * term3 % MOD;
        cout << ans << '\n';
    }
    return 0;
}

關鍵技巧總結

1. 質因子分解：大數分解為質因子冪次乘積
2. 積性函數分解：利用除數函數積性拆分計算
3. 等比數列求和公式：(p^(a+1)-1)/(p-1)
4. 模逆元處理除法：費馬小定理或擴展歐幾里得求逆
5. 快速冪：O(log n) 計算大指數模運算
6. 負數修正：(x - 1 + MOD) % MOD 避免負數

延伸知識：INF 常數技巧

const int INF = 0x3f3f3f3f; // 約 1e9
// 優點：memset 可直接初始化陣列（每字節 0x3f）
// 原理：0x3f3f3f3f = 1061109567，足夠大且無符號安全

此題完美展示了數論結構與模運算技巧在競賽程式設計中的實戰應用。