1.为了理解快速幂思想，先看一个例子：求5 ^ 19 = ？
因为19(10) = 10011(2)，所以有5 ^ 19 = 5 ^ (1+2+16) = (5^1) * (5^2) * (5^16);
将二进制分解思想实现，代码如下：
#include <stdio.h> int QuickPow(int p, int n, int m) /* 解决(p ^ n) % m = ?这类问题 */ { int ans = 1, base = p % m; // ans暂存当前结果,base为相应位基值 while(n >= 1) { if(n & 1) ans = (ans * base) % m; n = n >> 1; base = (base * base) % m; } return ans; } int main() { int res; res = QuickPow(2, 10, 1000); printf("res = %d ", res); return 0; }
2.费马小定理定义为：假如p是整数，m是质数，且p, m互质，即gcd(p, m) = 1，则(p^(m-1)) % m = 1。
下面通过一个具体应用 hdu还是幂取模 来加深理解：
题目大意：给定A,B,C，计算(A^(B^C)) % (e8+7) = ？(已知e8+7是素数，1<=A,B,C<=e9)
解题思路：（1）为了将费马小定理运用进来，先将(B^C)看成整体；
（2）e8+7是素数，但好像无法保证gcd(A, e8+7) = 1，尚有疑问？
（3）对(B^C)作拆分处理：(B^C) = ((B^C)/(e8+6)) * (e8+6) + (B^C) % (e8+6)；
（4）代入第(3)步且结合费马小定理得：(A^(B^C)) % (e8+7) = (A^((B^C)%(e8+6)) % (e8+7);
题目结果：两次运用快速幂，内层对(e8+6)取模，外层对(e8+7)取模。