求a^b%c（这就是著名的RSA公钥的加密方法） 算法1：直接将b个a相乘，利用a*b%c=((a%c)*b)%c,每一步都进行这种处理，解决了a^b可能太大存不下的问题，这个算法的时间复杂度是O(n)。当b很大时运行时间会很长 。 算法2：利用分治的思想，可以达到O(logn)。 可以把b按二进制展开为b=p(n)*2^n+p(n-1)*2^(n-1)+...+p(1)*2+p(0) 其中p(i) (0<=i<=n)为0或1 这样a^b=a^(p(n)*2^n+p(n-1)*2^(n-1)+...+p(1)*2+p(0)) =a^(p(n)*2^n)*a^(p(n-1)*2^(n-1))*...*a^(p(1)*2)*a^p(0) 对于p(i)=0的情况,a^p(i)*2^(i-1)=a^0=1,不用处理 我们要考虑的仅仅是p(i)=1的情况 a^(2^i)=(a^(p(i)*2(i-1)))^2 利用这一点，我们可以递推地算出所有的a^(2^i) 当然由算法1的结论，我们加上取模运算a^(2^i)%c=((a^(2(i-1))%c)*a^(2(i-1)))%c 于是再把所有满足p(i)=1的a^(2^i)%c按照算法1乘起来再%c就是结果
示例: 3^6%7=3^(2^2)*3^(2^1)%7 =((3^(2^1))^2%7)*(3^1*3^1%7) =(((3^1*3^1%7)%7)^2%7*2%7)%7 =(4*2)%7 =8%7 =1
当然算法可以进一步改进，比如二进制的每一位不必存起来，可以边求边用 经改进后代码如下：（输入a,k,m,求a^k%m)
long f(long a,long k,long m) { long b=1; while(k>=1) { if(k%2==1) b=a*b%m; a=a*a%m; k=k/2; } return b; }
转载于:https://www.cnblogs.com/noanti/archive/2011/10/11/2207687.html
相关资源：矩阵快速幂