1. 快速幂
1.5. 板子
1.6. 应用1：幂取模
1.7. 应用2：斐波那契数列

快速幂

问题引入

如何计算

朴素算法：让n个a相乘，时间复杂度为，当n特别大的时候，耗时特别长

而快速幂算法可以大大减少时间复杂度

n的分类

n为2的幂次时

如

我们可以用上一次的结果当作下一次的乘数：

这样只需要进行六次乘法就可以得出结果，时间复杂度为

即使用了倍增原理，将每次a的数量翻倍

n不为2的幂次时

我们可以将不是2的幂的数写成若干个2的幂的数的和，如

可以改写为，再根据以上方法计算

如何将n分解为2的幂次之和？

答案是位运算

让我们看看这几个数的二进制表示形式

会发现，目标数n的二进制中的1的个数与位置正好对应它分解后的数字

伪代码

function bigexp(a,n)
	r = 1
	while n!=0
		if n mod 2 == 1
			r = r*a
		a=a*a
		n=n/2
	return r

逻辑

行3，7：每次除二，让二进制位从右到左减少一位，相当于右移一位

行6：每次让翻倍（,,,,…）

行2，4，5，8：如果mod2==1，代表该位是1，则将该位代表的与结果相乘，即让幂次相加

位运算改进

n mod 2==1等同于n&1，n/2等同于n>>1

时间复杂度

，循环次数为n的二进制位数，对于整数n，它的二进制位数为

板子

int BigExp(int a,int n){
    int r = 1;
    while (n!=0){
        if (n&1) r = (r*a);
        a = (a*a);
        n >>= 1;
    }
    return r;
   }

应用1：幂取模

int ModExpFast(int a,int n,int m){
    int r = 1;
    while (n!=0){
        if (n&1) r = (r*a)%m;
        a = (a*a)%m;
        n >>= 1;
    }
    return r;
   }

注：

应用2：斐波那契数列

pair<int, int> fib(int n) {
  if (n == 0) return {0, 1};
  auto p = fib(n >> 1);
  int c = p.first * (2 * p.second - p.first);
  int d = p.first * p.first + p.second * p.second;
  if (n & 1)
    return {d, c + d};
  else
    return {c, d};
}

用矩阵形式表示斐波那契数列，如下图

我们可以发现它可以分为n个矩阵相乘再乘列向量F1 F0

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

红魔咖啡馆

【算法】快速幂

快速幂