NYOJ 420 P 次方求和：快速冪取模優化

題目

計算 `1^p + 2^p + ... + n^p mod 10003`。測試組數 T，每組給 n, p（n ≤ 1000, p ≤ 1000）。

快速冪取模

對每個底數 `i`，用二進制分解指數 `p` 計算 `i^p % 10003`：

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

完整代碼（C）

#include <stdio.h>
#define MOD 10003
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        long long n, p; scanf("%lld%lld", &n, &p);
        if (n == 0) { printf("0\n"); continue; } // 題目保證 n>0，但測試數據可能含 0
        long long sum = 1; // 1^p = 1
        for (long long i = 2; i <= n; i++) {
            long long a = i, b = p, t = 1;
            while (b) {
                if (b & 1) t = t * a % MOD;
                a = a * a % MOD;
                b >>= 1;
            }
            sum = (sum + t) % MOD;
        }
        printf("%lld\n", sum);
    }
    return 0;
}

複雜度分析

• 單次快速冪 O(log p)，p ≤ 1000 約 10 步。
• 外層循環 n ≤ 1000，總操作約 10^4 次/測試組，極快。
• 必須用 `long long` 防止中間乘積溢出（1000^2 < 2^31，但累加和可能大）。

避坑指南

• 輸入可能包含 n=0，需特判輸出 0（樣例無但測試數據有）。
• 模數 10003 為質數，但此處無需費馬小定理優化。
• 直接累加取模，無需矩陣快速冪或伯努利數公式（n,p 均較小）。