快速幂是一种利用二分思想计算乘方的算法，可以达到 $O(log_2 n)$。使用时注意根据场景修改数据类型，当数据范围过大且需要取余时，请使用快速幂模m算法。

代码实现：
1. 整数快速幂
计算 $a^n$，函数 quick_pow() 返回计算结果。

1
2
3
4
5
6
7
8
9
10
11
12
int quick_pow(int a, int n)
{
    int ans = 1;
    while (n)
    {
        if (n & 1)
            ans = ans * a;
        n >>= 1;
        a = a * a;
    }
    return ans;
}

2. 矩阵快速幂
设 $A$ 为 MAXN 阶方阵(只有方阵可以使用快速幂)，计算 $A^n$，函数 mat_quick_pow() 返回计算结果矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const int MAXN = 10; // 方阵的阶+1
typedef struct
{
    int m[MAXN][MAXN]; // 矩阵 下标从 1 开始
}Matrix;
Matrix mat_mul(Matrix a, Matrix b) // 矩阵乘法
{
    Matrix c;
    for (int i = 1; i <= MAXN; ++i)
        for (int j = 1; j <= MAXN; ++j)
        {
            c.m[i][j] = 0;
            for (int k = 1; k <= MAXN; ++k)
                c.m[i][j] += a.m[i][k] * b.m[k][j];
        }
    return c;
}
Matrix mat_quick_pow(Matrix a, int n)
{
    Matrix c = {0};
    for (int i = 1; i <= MAXN; ++i)
        c.m[i][i] = 1;
    while (n)
    {
        if (n & 1)
            c = mat_mul(c, a);
        n >>= 1;
        a = mat_mul(a, a);
    }
    return c;
}