算法笔记 快速幂

大家好，欢迎来到IT知识分享网。

该笔记想法来自与洛谷P1045 [NOIP2003 普及组] 麦森数一题改算法的时间复杂度为O(logn)

首先我们先思考一个问题:

平时的考试中计算幂次是怎么算的?:   比如2的10次方

是不是先想到脱口而出的乘法口诀表2*2=4然后继续往下乘2…..;

当然也有人说2的平方为4.算4的5次方就好了啊!

没错,快速幂的想法就来源于此.

来到最害怕的地方:看公式了,其实并没什么用.

(其实并没什么用.)继续聊上面的例子来认识这个公式:

刚刚说到计算4的5次方.如果在考试中(数学学霸除外)是不是(4^2)^2*4这样算的

也就是说,计算a的n次方，如果n是偶数（不为0），那么就先计算a的n/2次方，然后平方；如果n是奇数，那么就先计算a的n-1次方，再乘上a；递归出口是a的0次方为1。

int lpow(int a,int n){ if(n==0){ return 1; }else if(n%2==1){ return lpow(a,n-1)*a; }else{ int ans = lpow(a, n / 2); return ans * ans; } }

注意.这个ans在这里挺重要的,如果没有一个变量去记录a的n/2次幂.写成return lpow(a,n/2)*lpow(a,n/2)则会降低算法的时间复杂度.

在这道题中,要求对一个大素数取模，这是因为计算结果可能会非常巨大，但是在这里考察高精度又没有必要。这时我们的快速幂也应当进行取模，此时应当注意，原则是步步取模，如果MOD较大，还应当开long long。(long long在蓝桥杯中很有用/狗头)

递归虽然简洁，但会产生额外的空间开销。我们可以把递归改写为循环，来避免对栈空间的大量占用，也就是非递归快速幂。那么下面提供一个非递归算法.

我们换一个角度来引入非递归的快速幂。还是2的10次方，但这次，我们把10写成二进制的形式，也就是  。

现在我们要计算 ，可以怎么做？我们很自然地想到可以把它拆分为 ⋅ . 实际上，对于任意的整数，我们都可以把它拆成若干个 的形式相乘。而这些，恰好就是 2的1 次幂、2的2次幂……我们只需不断把底数平方就可以算出它们。

最初ans为1，然后我们一位一位算：

1010的最后一位是0，所以a^1这一位不要。然后1010变为101，a变为a^2。

101的最后一位是1，所以a^2这一位是需要的，乘入ans。101变为10，a再自乘。

10的最后一位是0，跳过，右移，自乘。

然后1的最后一位是1，ans再乘上a^8。循环结束，返回结果。

int qpow(int a, int n){ int ans = 1; while(n){ if(n&1){ //如果n的当前末位为1 ans *= a;} //ans乘上当前的a a *= a; //a自乘 n >>= 1; //n往右移一位 } return ans; }