快速幂

小管

发布于：Sep 26, 2020

710 words

3 min

算法描述

快速幂是一个$\theta$($logn$)的时间内计算$x^{n}$的小技巧，而暴力的计算需要$\theta$($n$)的时间。而这个技巧也常常用在非计算的场景，因为它可以应用在任何具有结合律的运算中。计算$\alpha$的n次方就是将n个$\alpha$乘在一起，然而当$\alpha$，n太大的时候，这种方法就不太实用。不过我们知道$a^{b+c}=a^b\ast a^c$,$a^{2b}=a^b\ast a^b$.二进制取幂的想法是，我们将取幂的任务按照指数的二进制表示来分割成更小的任务。

举个例子$3^{13}=3^{(1101)_2}=3^8\ast3^4\ast3^1$.

代码实现

递归算法

long long binpow(long long a, long long b) {
  if (b == 0) return 1;
  long long res = binpow(a, b / 2);
  if (b % 2)
    return res * res * a;
  else
    return res * res;
}

非递归


long long binpow(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}

模板：Luogu

应用

模意义下取幂

计算$x^n mod$$m$

这是一个非常常见的应用，既然我们知道取模运算不会干涉乘法运算，因此我们只需要在计算的过程中取模即可。

long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}

计算斐波那契数列

计算斐波那契数列的第n项

根据斐波那契数列的递推式$F_n=F_{n-1}+F_{n-2}$，我们可以构建一个2*2的矩阵来表示从$F_i$,$F_{i+1}$,$F_{i+2}$的变换。于是在计算这个矩阵的n次幂的时候，我们使用快速幂可以在更快的时间计算出结果。

高精度快速幂

题目大意：从文件中输入 P（1000<P<3100000），计算的最后 100 位数字（用十进制高精度数表示），不足 100 位时高位补 0。麦森数：题目链接

#include <bits/stdc++.h>
using namespace std;
int a[505], b[505], t[505], i, j;
int mult(int x[], int y[])  // 高精度乘法
{
  memset(t, 0, sizeof(t));
  for (i = 1; i <= x[0]; i++) {
    for (j = 1; j <= y[0]; j++) {
      if (i + j - 1 > 100) continue;
      t[i + j - 1] += x[i] * y[j];
      t[i + j] += t[i + j - 1] / 10;
      t[i + j - 1] %= 10;
      t[0] = i + j;
    }
  }
  memcpy(b, t, sizeof(b));
}
void ksm(int p)  // 快速幂
{
  if (p == 1) {
    memcpy(b, a, sizeof(b));
    return;
  }
  ksm(p / 2);
  mult(b, b);
  if (p % 2 == 1) mult(b, a);
}
int main() {
  int p;
  scanf("%d", &p);
  a[0] = 1;
  a[1] = 2;
  b[0] = 1;
  b[1] = 1;
  ksm(p);
  for (i = 100; i >= 1; i--) {
    if (i == 1) {
      printf("%d\n", b[i] - 1);
    } else
      printf("%d", b[i]);
  }
}