快速幂(模)

发表于 | 分类于 ，

1. 快速幂

一个非常简单的问题: \(n^k = ?\)。最直观简单的算法就是累乘了:

1
2
3
4
5
6
7
int Power(int n, int k)
{
    int ans = 1;
    for (int i = 0; i < k; ++i)
        ans *= n;
    return ans;
}

这个算法的时间复杂度为 \(O(k)\)。那么有没有比这个更快的方法呢？当然有了，这就需要用到快速幂算法了。

为了引入这个算法，我们首先换一个视角重新来审视一下上面的算法，我们知道:

\[ n^k = n^{(1 + 1 + \cdots + 1)} = n * n * \cdots * n \]

我们的第一个算法就是用最右边的式子来替代最左边的式子，由于 k 等于 k 个 1 相加，所以一共要计算 k 次。

那么有没有方法可以把乘法的次数降下来呢？这就需要换一个分解 k 的方法了，原来我们用纯粹的加法计算来进行分解，现在我们换用二进制的分解法。以 \(k = 13\) 为例

\[ 13 = (1101)_B = 1 * 2^0 + 0 * 2^1 + 1 * 2^2 + 1 * 2^3 \]

很显然这样的划分方式要精简的多，用这样的方式来计算幂，算法就变成了:

\[ n^{11} = n^{2^0} * n^{2^2} * n^{2^3} * n^{2^4} \]

算法从 \(O(k)\) 降到了 \(O(\log{k})\)。

实现如下:

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

注意到这个算法的实现相当有技巧性:

  1. 总体框架:
1
2
3
4
5
6
while (k)
{
    if (k & 1)
    //...
    k >>= 1;
}

这其实就是在遍历 k 的二进制表示，k & 1 表示当前 k 最低位的数值；k >>= 1 则是将 k 不断逻辑右移，相当于 k /= 2。

  1. base的用处

base 在这里的作用相当于 \(n^{2^i}\)，初始的时候它是 \(n^{2^0} = n\)，然后不断变为 \(n^{2^1}, n^{2^2}, n^{2^3}, \dots\)

  1. ans
1
2
if (k & 1)
    ans *= base;

这个其实就是在计算 \(x * n^{2^i}\)，且只有对应的二进制位是 1 时才会计算。

2. 快速幂模

求 \(n^k \bmod p\) 的 \(O(\log{k})\) 算法。

基于上述的快速幂和以前提到过的公式:

\[ \begin{cases} (a * b) \bmod p = (a \bmod p * b \bmod p) \bmod p\\ (a ^ b) \bmod p = ((a \bmod p) ^ b) \bmod p \end{cases} \]

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