快速幂

基本思想

当我们需要计算

\[ a^b \bmod p \]

时，如果直接进行 $b$ 次结果相乘，时间复杂度是 $O(b)$，很慢。

而利用 二进制分解 和 指数的性质，我们可以将 $a^b$ 进行高效率计算。

---

递归方法

\[a^b=\begin{cases} 1 & \text{if } b=0\\ a^{\frac{b}{2}}\cdot a^{\frac{b}{2}} & \text{if } b\equiv 0\bmod 2\\ a^{\frac{b}{2}}\cdot a^{\frac{b}{2}}\cdot a & \text{if } b\equiv 1\bmod 2\\ \end{cases}\]

代码实现

constexpr int p = 1e9 + 7;
long long qpow(long long a, long long b)
{
    if (b == 0) return 1;
    long long sum = qpow(a, b / 2);
    if (b % 2 == 0)
    {
        return sum * sum % p;
    }
    else
    {
        return sum * sum % p * a % p;
    }
} 

时间复杂度： $O(\log b)$

二进制分解

件于任何一个正整数 $b$，都可以表示成数个 $2$ 的非负指数求幂之和：

• $5 = 1 + 4 = 2^0 + 2^2$
• $7 = 1 + 2 + 4 = 2^0 + 2^1 + 2^2$
• $20 = 4 + 16 = 2^2 + 2^4$

那么：

\[ a^b = a^{2^{k_1}} \times a^{2^{k_2}} \times \dots \times a^{2^{k_m}} \]

其中 $k_i$ 是 $b$ 二进制中为 $1$ 的位置

因此，只需要 $O(\log b)$ 次指数计算，就可以快速计算 $a^b \mod p$

---

示例

如果需要计算 $3^{13}$：

\[ 3^{13} = 3^{(1101)_2} = 3^8 \times 3^4 \times 3^1 \]

只需计算 $3^1, 3^2, 3^4, 3^8$ ，然后依据二进制位为 $1$ 的部分相乘即可

---

实现代码

constexpr int p = 1e9 + 7;
long long ksm(long long a, long long b)
{
    long long res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

其余特殊情况

• 模数过大，例如 $p$ 的值超过 int 的范围。
  • 此时可能导致 res * a 或 a * a 的结果超过 long long 的范围。
  • 可以使用 __int128 类型做中间运算，然后取模。

constexpr long long p = 1e12 + 39;
long long ksm(long long a, long long b)
{
    // a = a % p; // 如果 a 很大可以提前取余，b 不能取余 
    long long res = 1;
    while (b)
    {
        if (b & 1) res = (__int128)res * a % p;
        a = (__int128)a * a % p;
        b >>= 1;
    }
    return res;
}

注意

• 参数 a 和 b 可能很大，所以使用 long long
• 每次乘法操作后都应与 p 取余，防止溢出。
• b & 1 用于判断最低位是否为 $1$
• b >>= 1 表示将 b 右移 $1$ 位，即除以 $2$

时间复杂度： $O(\log b)$

---