HDU 1452 Happy 2004：2004^X 約數和模 29（費馬小定理 + 模逆元）

數學推導

2004 = 2² × 3 × 167。
2004^X = 2^2X × 3^X × 167^X。
約數和公式：
σ(2004^X) = (2^2X+1−1)/(2−1) × (3^X+1−1)/(3−1) × (167^X+1−1)/(167−1)
= [2^2X+1−1] × [3^X+1−1] × [167^X+1−1] / 332。

模 29 運算

要求 σ mod 29。分母 332 需求模 29 逆元。
332 mod 29 = 13。13 的逆元：13 × 9 = 117 ≡ 1 (mod 29) → 逆元 = 9。
故答案 = (分子 mod 29) × 9 mod 29。

指數縮減（費馬小定理）

29 為質數，對任意 a 不被 29 整除，a²⁸ ≡ 1 (mod 29)。
故 a^e mod 29 = a^{e mod 28} mod 29。
指數分別模 28：
2X+1 → (2X+1) mod 28
X+1 → (X+1) mod 28

代碼

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

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

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

擴展：模逆元通用求法（擴展歐幾里得）

long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}
long long mod_inv(long long a, long long m) {
    long long x, y;
    long long g = exgcd(a, m, x, y);
    return (g == 1) ? (x % m + m) % m : -1;
}
// mod_inv(332, 29) == 9