本文转载自微信公众号“bigsai”，作者大赛。转载本文请联系bigsai公众号。前言大家好，我是bigsai。有个小哥在offer里问了一个关于快功率的问题。这是一个快速概述！什么是快速功率？力量。你可能会疑惑，求n的次方，计算n次的叠加不就可以了吗？当n很大时，如果需要最后的有效尾数等信息，这可能超出了计算机的计算范围。多快？fastpower的时间复杂度为O(log?n)，与简单的O(n)相比，效率有了很大的提升。一个20位长度的数字，64次之内就可以搞定，看多快）。使用了多少？快幂属于数论范畴。本来是ACM经典算法，现在各个大厂对算法的要求越来越高，fastpower的应用场景低很多，相对于simplemethod有了很大的提升，所以掌握fastpower算法已经是一个更合格工程师的必备要求了！下面我们就来详细了解一下快幂算法吧！^10)%1000你可以这样写：intva=1;for(inti=0;i<10;i++){va*=2;}System.out.println(va%10000);熟悉的1024没问题，一共计算了10次。但是，如果要求您计算(2^50)%10000怎么办？你可能会很高兴，这是想难倒我吗？我知道int只有32位，如果50位超出范围，就会抛出值越界的异常。你可以使用long一次，long有64位！longva=1;for(inti=0;i<50;i++){va*=2;}System.out.println(va);System.out.println(va%10000);计算了50次，得到了结果。正当你暗自高兴的时候，另一个可怕的问题又来了：允许你计算(2^1e10)%10000并且不允许使用Java大数。你为此烦恼。措施。这时bigsai小哥让你去百度下载取模计算，你才恍然大悟，原来自己在纸上写了几个公式：(a+b)%p=(a%p+b%p)%p(1)(a-b)%p=(a%p-b%p)%p(2)(a*b)%p=(a%p*b%p)%p(3)a^b%p=((a%p)^b)%p(4)你还算聪明，一眼就发现了规律：(a*b)%p=(a%p*b%p)%p(3)(2*2*2···*2)%1e10=[2*(2*2···*2)]%1e5=(2%1e5)*(2*2···*2%le5)%1e5有了这个递归你就明白了：每二次乘法都是取模的。聪明的piapia写了下面的代码，却又发现了一个问题：为什么跑不出来？我们上班族需要对电脑的运行速度和价值有一个大概的了解。循环体中的不同操作需要不同的时间，所以当你的程序循环到1e6或1e7时你需要非常非常小心。如果循环体有更多的逻辑或操作，它可能会非常非常慢。不甘失败，机智的小女孩开始研究计数法则，并把这个公式写在手上、肩膀上、小纸条上。边吃边睡边看：然后小姑娘突然发现了其中的奥秘，n的次方可以拆分成平方计算，剩下n/2的力量：现在你明白什么是快的力量了吧，但是小的妹子可能有点过头了，但是她还是跟我说了很多：快速指数的实现至于快速求幂，我们如何实现这个算法呢？说的好，确实有递归和非递归的实现方式，只是递归用的多了点。实现时只要注意奇偶校验和停止条件即可。奇数问题可以转化为偶数问题：2*2*2*2*2=2*(2*2*2*2)奇数问题可以转化为偶数问题。这里，递归求解如下：longc=10000007;publiclongdivide(longa,longb){if(b==0)return1;elseif(b%2==0)//偶数情况returndivide((a%c)*(a%c),b/2)%c;else//奇数情况return%c*divide((a%c)*(a%c),(b-1)/2)%c;}非递归实现也不难，控制好循环条件即可://找到a^b%1000000007longc=1000000007;publiclongdivide(longa,longb){a%=c;longres=1;for(;b!=0;b/=2){if(b%2==1)res=(res*a)%c;a=(a*a)%c;}returnres;}对于非递归，你可能有点模糊为什么偶数情况下res不赋值。这里有两点：在奇数的情况下，res只是收集和相乘。到时候单a最后会减为1，a最后会和res相乘。不要担心错过理想的状态总是均匀的。最后直接得到a的模值。如果还是不明白，可以用这张图来解释一下：matrixfastpower，你以为这就完了吗？虽然快速功率的主要内容就是以上内容，但是总有很多好心人能够找到非常有趣的规律——矩阵快速功率。如果你还没有听过，我建议你仔细看看才能找到答案。斐波那契数列大家都知道：规则：前几个斐波那契数列是：0,1,1,2,3,5,8,13,21,34,...Fibonaccifromhand从push方法可以看出说是指数增长，所以多几位就是爆发式增长，所以往往需要最后几位的结果。有了之前的取模计算公式，溢出不是问题，但是如果n非常非常大，如何快速计算就成了一个新问题。我们来看下面这组公式：f(n+1)=f(n)+f(n-1)f(n)=f(n)如果把f(n)和f(n-1)成一个矩阵中（一行两列）：[f(n+1),f(n)]你能找到[f(n),f(n-1)]之间的规律吗？答案是有规律的，看上面的公式就知道：[f(n+1),f(n)]=[f(n)+f(n-1),f(n)][11]=[f(n),f(n-1)]*[10][11][11]=[f(n-1),f(n-2)]**[10][11]=········所以现在你可以知道它的规律了，所以一直迭代到f(2),f(1)都为1，所以这个斐波那契的计算是：并且这个矩阵有很多次幂，可以用fastpower嘛，原理是一样的，只需要写一个矩阵乘法，这里有一个模板，可以快速对矩阵求幂求斐波那契第n项的后三位，你可以用这个来试试poj3070的题目。publicintFibonacci(intn){n--;//矩阵是两项inta[][]={{1,1},{1,0}};//快速求幂的矩阵intb[][]={{1,0},{0,1}};//存储缺失单奇数矩阵和结果，初始单位矩阵inttime=0;while(n>0){if(n%2==1){b=matrixMultiplication(a,b);}a=matrixMultiplication(a,a);n/=2;}returnb[0][0];}publicint[][]matrixMultiplication(inta[][],intb[][]){//intx=a.length;//a[0].length=b.length满足条件inty=b[0].length;//判断每个有多少个intc[][]=newintrowhas[x][y];for(inti=0;i
