NYOJ 420 p次方求和：快速冪取模計算 Σ(i^p) mod 10003

問題描述

多測試用例，每個給 n, p (n≤1000, p≤1000)。求 S = Σ_{i=1}^{n} i^p mod 10003。

快速冪取模

計算 a^b mod m：
pow_mod(a, b, m) = 1 if b==0 else (pow_mod(a, b/2, m)^2 * (b%2?a:1)) mod m。
遞歸或迭代均可，O(log b)。

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 10003;
int mod_pow(int a, int b) {
    long long res = 1, base = a % MOD;
    while (b) {
        if (b & 1) res = res * base % MOD;
        base = base * base % MOD;
        b >>= 1;
    }
    return (int)res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n, p; cin >> n >> p;
        int sum = 0;
        for (int i = 1; i <= n; ++i) {
            sum = (sum + mod_pow(i, p)) % MOD;
        }
        cout << sum << '\n';
    }
    return 0;
}

複雜度

• 時間：O(T × n × log p) ≤ 1000 × 1000 × 10 = 1e7，極快。
• 空間：O(1)。

關鍵點

• 模數 10003 為質數，但本題無需費馬小定理優化（p 不大）。
• 快速冪迭代版無遞歸開銷，更推薦。
• 同餘定理：(a+b) mod m = (a mod m + b mod m) mod m，逐項累加取模。

基礎數論編程練習：快速冪 + 取模累加，代碼簡潔標準。