計算A^B mod 1000，多組輸入，A=0且B=0結束。A,B均為非負整數。
int mod_pow(int a, int b, int mod) {
long long res = 1, base = a % mod;
while (b > 0) {
if (b & 1) res = (res * base) % mod;
base = (base * base) % mod;
b >>= 1;
}
return (int)res;
}
#include <stdio.h>
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;
}
| 要點 | 說明 |
|---|---|
| 中間結果溢出 | 用long long承載乘積，1000*1000=1e6遠小于2^31，但良好習慣 |
| 模數分配律 | (a*b)%m = ((a%m)*(b%m))%m，每步取模防止溢出 |
| B=0情況 | A^0 = 1 (含0^0，題目通常定義為1或作為終止條件) |
| 負數處理 | 題目非負整數，無需處理；若擴展至負指數需模逆元 |
printf("%03d\n", mod_pow(n, m, 1000));
long long mod_pow_ll(long long a, long long b, long long mod) {
__int128 res = 1, base = a % mod; // GCC/Clang支援128位
while (b) {
if (b & 1) res = (res * base) % mod;
base = (base * base) % mod;
b >>= 1;
}
return (long long)res;
}
φ(1000) = 1000 × (1-1/2) × (1-1/5) = 400
若gcd(A,1000)=1，則A^400 ≡ 1 (mod 1000)，可將指數B %= 400。但1000=2³×5³非質數，且A可能與1000不互質，通用快速冪更穩健。
