快速幂的应用

快速幂应用的推广

$a^b$

来简单复习一下快速幂
对于一个要求计算 的题目， ，若用朴素算法的复杂度是O(b)

    int ans = a;
    for(int i = 1; i <= b; ++i){
      ans = ans * a;
    }

但倘若我们能让b二进制分解的话，可以优化该复杂度
假设当b = 8时，b的二进制表示是 1000，即可以表示为

    int ans = 1;
    while(b){
      a *= a;
      b >>= 1;
    }
    ans = ans * a;

因此我们只需计算b二进制表达式下的每一个1到答案即可

int qm(int a, int b){
      int ans = 1;
      while(b){
        if(b & 1) ans *= a;
        a *= a;
        b >>= 1;
      }
      return ans;
}

在取模p的情况下

int qm(int a, int b, int p){
      int ans = 1;
      while(b){
        if(b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
      }
      return ans;
}

那么快速幂除了做简单的数的幂次，还能干些啥呢？

对于一个 Fibonacci 数列，我们知道它的递推公式

但是对于，其O(n)的复杂度也是很大的，

我们可以发现这个其实可以用矩阵表示

此时我们就可以用快速幂计算这个矩阵，把复杂度从O(n)降低到O(logn)

举个例题：

对于前 n 项斐波那契数列

我们知道，

我们移项使得 ，

也就是

然后我们将n项列出来，

我们将所有式子累加

所以我们可以用快速幂计算出

#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<=m;++i)
#define int long long
using namespace std;
int ans[2] = {1, 0};
int A[2][2] = {
    {1, 1},
    {1, 0}
};
int n, p;
void mul(int a[], int b[][2]){
    int c[2] = {0};
    c[0] = a[0] * b[0][0] + a[1] * b[0][1];
    c[1] = a[0] * b[1][0] + a[1] * b[1][1];
    a[0] = c[0] % p;
    a[1] = c[1] % p;
}
void cal(int a[][2], int b[][2]){
    int c[2][2] = {0};
    rep(i, 0, 1){
        rep(j, 0, 1){
            rep(k, 0, 1){
                c[i][j] += a[i][k] * b[k][j] % p;
            }
        }
    }
    rep(i, 0, 1){
        rep(j, 0, 1){
            a[i][j] = c[i][j] % p;
        }
    }
}
signed main()
{
    cin >> n >> p;
    n += 2;
    if(p == 1){
        cout << 0;
        return 0;
    }
    while(n){
        if(n & 1) mul(ans, A);
        cal(A, A);
        n >>= 1;
    }
    printf("%lld", ans[1] - 1);
    return 0;
}

快速幂最常用的是还可以用来求逆元，由费马小定理得：

当b, m满足互质时，且 a 可以整除 b，
使得

得证：
对 a % p != 0 时

a % p 的逆元为
即可以用快速幂 求得。

在b站up主视频结尾看到这样的一个思考题

可以先自己思考一下
→
→
→
→
→
→
→
→
→
→
→
→
→
→
→

我们不妨把每种元素看成一个数，然后转换成一个列矩阵

对于第一次变换，我们可以给其左乘以一个 6 * 6 的方阵

于是

我们可以发现每一次置换就是左乘一个方阵，所以对于 n 次置换，那么答案就是

可以用快速幂求得。

这是前几天拍的月全食，红色已经过去了