HDU 3063 Play Game 題解：大整數模運算與數學公式推導 O(|n|) 解法

題目大意

n 個小孩排成隊，編號 1..n。第 i 個小孩手持數字 i(i+1)(i+2)。第 k 個小孩需報出前 k 個數字之和。求第 n 個小孩報出的數值模 9999。
n ≤ 10¹⁰⁰ (超大整數，以字串輸入)。

數學推導

單項：f(i) = i(i+1)(i+2) = i³ + 3i² + 2i

前 n 項和：

S(n) = Σ f(i) = Σi³ + 3Σi² + 2Σi

代入求和公式：

• Σi = n(n+1)/2
• Σi² = n(n+1)(2n+1)/6
• Σi³ = [n(n+1)/2]²

化簡得驚人簡潔公式：

S(n) = n(n+1)(n+2)(n+3) / 4

驗證

• n=1: 1×2×3×4/4 = 6 ✓
• n=2: 2×3×4×5/4 = 30 ✓
• n=3: 3×4×5×6/4 = 90 ✓

大整數模運算技巧

因 n 極大 (10¹⁰⁰)，需以字串處理。利用模運算性質：

(a × b) mod m = [(a mod m) × (b mod m)] mod m

但分母 4 需處理模逆元。因 mod = 9999 = 9 × 11 × 101，4 與 9999 不互質，**無模逆元**。

關鍵突破：擴大模數法

計算 X = n(n+1)(n+2)(n+3) mod (4 × 9999 = 39996)，然後 S = X / 4 (整除)。

證明：n(n+1)(n+2)(n+3) 為 4 連續整數乘積，**必能被 4 整除**。設真值為 4k。
X = 4k mod 39996 = 4k - 39996×q = 4(k - 9999q) → X 為 4 的倍數。
X/4 = k - 9999q ≡ k (mod 9999) ✓

完整 C++ 程式碼

#include 
using namespace std;
const int MOD = 9999;
const int BIG_MOD = 4 * MOD;  // 39996

// 字串轉模值
int strMod(const string& s, int mod) {
    long long res = 0;
    for (char c : s) {
        res = (res * 10 + (c - '0')) % mod;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string n_str;
    while (cin >> n_str) {
        long long n_mod = strMod(n_str, BIG_MOD);
        
        // 計算 n, n+1, n+2, n+3 模 BIG_MOD
        long long a = n_mod;
        long long b = (n_mod + 1) % BIG_MOD;
        long long c = (n_mod + 2) % BIG_MOD;
        long long d = (n_mod + 3) % BIG_MOD;
        
        long long prod = a;
        prod = (prod * b) % BIG_MOD;
        prod = (prod * c) % BIG_MOD;
        prod = (prod * d) % BIG_MOD;
        
        int ans = (prod / 4) % MOD;
        cout << ans << '\n';
    }
    return 0;
}

複雜度分析

• 時間：O(|n|) — 單趟掃描字串長度 (≤100 位)。
• 空間：O(1) — 僅常數變數。

核心技巧總結

1. 多項式求和化簡找閉合公式。
2. 分母與模數不互質時，擴大模數至 LCM(分母, 模數)，整除後再取模。
3. 大整數模運算：字串逐位累積 (res*10 + digit) % mod。

延伸思考：若模數為質數 p，分母 d 不被 p 整除，可用費馬小定理求模逆元 d^(p-2) mod p。本題因模數合數且分母 4 與模數不互質，擴大模數法更通用、優雅。