什么是快速幂乘算法？
快速幂函数算法有助于计算指数非常大的幂。 传统的求幂算法(时间复杂度非常高(o ) (指数n ) )是因为如果指数n非常大，则需要执行的循环操作的次数也非常大。 所以，我们快速幂算法的核心思想是在每一步将指数分成两半，并对相应的底数进行平方运算。 这不仅会减小非常大的指数，而且会减少执行的周期数，但最终显示的结果不会改变。 让我们来看一个简单的例子。 是3的10次方
3 ^ 10=3*3*3*3*3*3*3*3*3*3*3*3*3* 3
考虑一下尽量缩小指数的方法吧。 这里的指数是10。 把这个变形一下吧
3^10=(3*3) ) (3*3) )3) ) )3*3) )
3^10=(3*3) 5
3^10=9^5
此时指数从10扩大到5 (缩小一半)，而底部从3扩大到9 )倍。 3 )求10本来需要10次循环操作，求9 ) 5只需要5次循环操作，而3 ) 10变成了9 ) 5。 1次)底的平方操作)减少了原来一半的环路量。 特别是乘方特别大时
现在，我们的问题是如何将指数5减半。 我们都知道5是奇数，5的一半是2.5。 但是我们知道指数不是小数，所以我们不能那么容易粗暴地直接执行5/2。 但是，这里还有另一种方法。 可以表示9^5
9^5=(9^4) )9^1) ) ) ) 0
此时，取出了底部的一次侧。 这里就是9^1。 先单独取出这个9^1。 剩下的9^4是将指数缩小一半，将底数平方的上述操作(命名吧。 “缩指数、扩底数”)
9^5=(81^2) )9^1) ) ) ) 0
指数缩小一半，底数平方操作
9^5=(6561^1) ) )9^1) ) ) ) ) ) ) 0
此时，我们发现指数已经变成了另一个奇数1。 从上面操作指数为奇数时，应该会提取底部的一次侧。 这里就是6561^1。 先单独取出这个6561^1，此时指数为0。 也就是说，不能进行“缩短指数、延长底部”的操作。
9^5=(6561^0) )9^1) ) 6561^1) ) ) 6561^1)=9*6561=59049
最后的结果是9*6561，可以看出9是怎么产生的。 指数为奇数5时，底数是9吗？ 6561是怎么产生的呢？ 指数为奇数1时，那时的底数是6561吗？ 因此，最后求幂的结果实际上可以找到变化过程中指数为奇数时底数的乘积的规律。
这个快速幂的代码可以写为：
长龙快速电源(长龙基础，长龙电源)。
{
长长结果=1；
是while (电源0 )
{
if (电源%2==1) ) ) )。
result=(result*base ) 00；
功率=功率/2；
基本=(基本*基本) 00；
}
返回结果；
}
但是，对于上述代码，细心的学生应该看起来可以再优化一些，以便程序可以节省更多的时间。
在c语言中，power%2==1可以替换为更快的“位运算”，就像power1一样。 因为如果power是偶数，则该二进制表示的最后一位一定是0； 如果电源为奇数，则二进制表示的最后一位必须为1。 将他们分别与一进制进行与运算，得到功率二进制的最后一位数字。 0的话是偶数，1的话是奇数。 例如5为奇数，则51=1； 6为偶数时，61=0； 因此，奇偶校验数的判断可以置换为“比特运算”。 同样，power=power/2也可以用更快的“位运算”代替。 我们只要将power的二进制表示向右移动1位，就会变成原来的一半。
终极优化快速幂乘算法代码：
长龙快速电源(长龙基础，长龙电源)。
{
长长结果=1；
是while (电源0 )
{
等效于if (电源1 ) /这里为if )电源%2==1
result=(result*base ) 00；
电源=1； //这里等价于power=power/2
基本=(基本*基本) 00；
}
返回结果；
}