快速幂

问题引入

如何计算\(a^n\)

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

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

n的分类

n为2的幂次时

如\(a^{64}\)

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

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

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

n不为2的幂次时

我们可以将不是2的幂的数写成若干个2的幂的数的和，如\(a^{105}\)

可以改写为\(a^{1+8+32+64}\)，再根据以上方法计算

如何将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：每次让\(a^{n}\)翻倍（\(a^{1}\),\(a^{2}\),\(a^{4}\),\(a^{8}\),\(a^{16}\)…）

行2，4，5，8：如果mod2==1，代表该位是1，则将该位代表的\(a^{n}\)与结果相乘，即让幂次相加

位运算改进

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

时间复杂度

\(O(\log n)\)，循环次数为n的二进制位数，对于整数n，它的二进制位数为\(1+\lfloor\log_2n\rfloor\)

板子

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;
   }

注：\((a \times b)\mod m=((a\mod m)\times(b\mod m))\mod m\)

应用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个矩阵相乘 \[ \left( \begin{array}{cc} 1 & 1\\ 1 & 0 \end{array} \right) ^{n} \] 再乘列向量F1 F0

红魔咖啡馆

【算法】快速幂

快速幂