快速幂旨在 $O(\log_2 N)$ 次的时间复杂度下计算 $a ^ n$ 的结果，相比于传统 $O(N)$ 的暴力写法更加高效。

原理

以计算 $a ^ {11}$ 为例。

我们可以先将这个数拆分，保证每一个指数都是 $1$ 或 $2$ 的倍数，例如，$a ^ {11} = a ^ {8 + 2 + 1} = a ^ 8 \times a^2 \times a ^ 1$。

这样做运用了倍增的思想：只要知道 $a$，就可以知道 $a ^2$，再乘以自身就可以知道 $a ^ 4$……

那么我们如何找出这个拆分的方式呢？想到二进制：将 $11$ 转化成二进制：$11_{10} = 1011_2 = 2^3 + 2^1 + 2^0 = 8 + 2 + 1$。这就是我们最后要拆分出来的结果。

要更好地计算二进制，就可以运用位运算。可以得到快速幂的代码。

快速幂模板

P1226 【模板】快速幂

#include <iostream>
#define ll long long

using namespace std;

ll fastPow(ll a, ll n, ll mod)
{
    ll ans = 1;
    a %= mod;
    while(n)
    {
        if (n & 1) // 判断二进制最后一位是不是 1
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return ans;
}

局限性

如果 $a$ 太大，即使是快速幂也会出现溢出的情况。这时候需要使用高精度，或者 Python 来进行运算。但这会显著降低运行效率。

如果 $n$ 太大，例如 $10 ^ {200000000}$，即使是 $O(\log_2 N)$ 的时间复杂度也会出问题，这时候就需要使用更复杂的写法：扩展欧拉定理。

扩展欧拉定理模板：计算 n 极大时的快速幂

P5091 【模板】扩展欧拉定理

（本题需要求 $a ^ b \mod m$ 的结果，下文中所有的描述将以这三个字母作为命名。）

欧拉定理的内容不在此文中赘述。其时间复杂度可以认为是 $O(len_b + \sqrt m + \log_2 m)$。

#include <iostream>
#define ll long long

using namespace std;

ll euler_phi(ll n)
{
    ll ans = n;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
        {
            ans = ans / i * (i - 1);
            while (n % i == 0)
                n /= i;
        }
    if (n > 1)
        ans = ans / n * (n - 1);
    return ans;
}

ll fast_pow(ll a, ll n, ll mod)
{
    ll ans = 1;
    a %= mod;
    while (n)
    {
        if (n & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return ans;
}

ll read(ll mod)
{
    ll x = 0, w = 1;
    char ch = 0;
    bool check = false;
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = ((x << 3) + (x << 1) + (ch - '0'));
        if (x >= mod)
        {
            check = true;
            x %= mod;
        }
        ch = getchar();
    }
    if (x >= mod)
    {
        check = true;
        x %= mod;
    }
    if (check)
        x += mod;
    return x * w;
}