快速幂求余算法（OJ T1128）求ab%c（这就是著名的RSA公钥的加密方法）当a,b很大时，直接求解这个问题不太可能，你能想到哪些优化呢？算法1：直观上，也许最容易想到的是利用a*b%c=(a%c)*b)%c，这样每一步都进行这种处理，这就解决了ab可能太大存不下的问题，但这个算法的时间复杂度依然是O(n)，根本没有得到优化。当b很大时运行时间会很长算法2：另一种算法利用了分治的思想，可以达到O(logn)。 可以把b按二进制展开为b=p(n)*2n+p(n-1)*2(n-1)+.+p(1)*2+p(0) 其中p(i) (0=i=n)为0或1 这样ab=a(p(n)*2n+p(n-1)*2(n-1)+.+p(1)*2+p(0) =a(p(n)*2n)*a(p(n-1)*2(n-1)*.*a(p(1)*2)*ap(0) 对于p(i)=0的情况,ap(i)*2(i-1)=a0=1,不用处理，我们要考虑的仅仅是p(i)=1的情况，a(2i)=(a(p(i)*2(i-1)2
