UVa 374

　　题目大意：计算R = B^P mod M，根据模运算的性质计算。

　　正常计算会超时，可以用分治的思想降低时间复杂度。不过如果遇到0⁰，结果...话说0⁰的结果是1吗？忘了都...

 1 #include <cstdio>
 2 
 3 int powMod(int base, int exp, int mod)
 4 {
 5     if (exp == 0)  return 1;
 6     int res = powMod(base, exp>>1, mod);
 7     res = (res * res) % mod;
 8     if (exp & 0x1 == 1)  res = (res * base) % mod;
 9     return res;
10 }
11 
12 int main()
13 {
14 #ifdef LOCAL
15     freopen("in", "r", stdin);
16 #endif
17     int b, p, m;
18     while (scanf("%d%d%d", &b, &p, &m) != EOF)
19     {
20         int res = powMod(b%m, p, m);
21         printf("%d
", res);
22     }
23     return 0;
24 }

View Code