C語言模冪運算：快速求 A^B 末三位數字

問題描述

計算 n^m mod 1000，輸出結果（無前導零）。多組測試，n=m=0 結束。n,m 為非負整數。

核心算法：模冪性質

(a×b) mod p = ((a mod p) × (b mod p)) mod p

迭代 m 次：result = (result * (n%1000)) % 1000。時間 O(m)。

原始代碼分析

sum = 1;
for i=1..m: sum = ((n%1000) * sum) % 1000;

正確但 m 可能很大（如 10⁹），O(m) 會超時。需用 快速冪（二進制指數法） 優化至 O(log m)。

快速冪優化實現

#include <stdio.h>

int mod_pow(int base, int exp, int mod) {
    int result = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        if (n == 0 && m == 0) break;
        printf("%d\n", mod_pow(n, m, 1000));
    }
    return 0;
}

關鍵優化點

• O(log m) 複雜度：指數每輪減半，m=10⁹ 僅需 ~30 次迴圈。
• 避免溢位：result * base 最大 999*999 < 10⁶，int 安全。若模數較大需用 long long 或 __int128。
• 處理 m=0：n⁰=1（含 0⁰ 定義為 1，符合大多數編程約定）。

進階：歐拉定理進一步優化

若 gcd(n,1000)=1，由歐拉定理 n^φ(1000) ≡ 1 (mod 1000)，φ(1000)=400。可將指數模 400 減少。但 1000=2³×5³ 非質數，且 n 可能不互質，通用性不如快速冪。

應用場景

• RSA 加密/解密核心運算（模數為大質數乘積）。
• 大數末幾位數字計算（如費波那契數列末位、階乘末非零位）。
• 哈希函數、偽隨機數生成器（線性同餘法）。