快速幂

                     

贡献者: 待更新

   快速幂算法和前缀和算法的作用一样,都是优化某些操作的时间复杂度。所以快速幂算法就是可以很快速的:求 $a$ 的 $b$ 次方模 $p$ 的结果。

   数据范围:$0 \le a,b \le 10^9$,$1 \le p \le 10^9$。

   根据数据范围可知朴素做法会超时,但是可不可以用 pow 函数来做呢? 答案是不行的。

   因为 pow 函数得到的值是 double 类型,有效数字只有 $15\sim16$ 位,并不能求出精确值。这道题目是让我们求出精确值对某个数的余数,所以这道题我们可以使用快速幂算法来做。

   如果 $b$ 在二进制下有 $k$ 位,其中第 $i$($0 \le i \le k$)位的数字是 $c_i$,有:

\begin{equation} b = c_{{k-1}^{\ 2^{\ k-1}}}+c_{{k-2}^{\ 2^{\ k-2}}}+\cdot\cdot\cdot+c_{{0}^{\ 2^{\ 0}}}~, \end{equation}
于是:
\begin{equation} a^b= a^{c_{{k-1}^{\ \ 2^{\ k-1}}}} \ *\ a^{c_{{k-2}^{\ \ 2^{\ k-2}}}} \ * \cdots * \ a^{c_{{0}^{\ 2^{\ 0}}}}~. \end{equation}

   又因为: $$ a^{2^{i}} = (a^{2^{i-1}})^2~, $$

   所以我们可以通过上一次计算的结果来计算下一次计算的结果。 这公式这么复杂,到底怎么理解呢?手动模拟一下就可以啦!

   例子:求 $2^{12} \bmod 1$ 的值,结果是 $4096$。

   让我们把值代入到公式中看看:

   $ (a) _ {10} = 2, (b) _ {10} = 12, (p) _ {10} = 1$

   $ (a) _ 2 = 10, (b) _ 2 = 1100, (p) _ 2 = 1 $

   如果 $b$ 在二进制下有 $k$ 位,其中第 $i$($0 \le i \le k$)为的数字是 $c_i$,有:

   $k = 4$、$k - 1 = 3$、$k - 2 = 2$、$k - 3 = 1$、$k - 4 = 0$。

   $c_3 = 1$、$c_2 = 1$、$c_1 = 0$、$c_1 = 0$。

   $$ \begin{aligned} &c_{k - 1} = c_3 = 1~,\\ &2 ^ {k - 1} = 2 ^ 3 = 8~,\\ &c_{{k-1}^{\ 2^{\ k-1}}} = c_{{3}^{\ 2^{\ k-1}}} = c_{{3}^{\ 2^{\ 3}}} = 1^8 = 8~. \end{aligned} $$

   $$ \begin{aligned} &c_{k - 2} = c_2 = 1~,\\ &2 ^ {k - 2} = 2 ^ 2 = 4~,\\ &c_{{k-2}^{\ 2^{\ k-2}}} = c_{{2}^{\ 2^{\ k-2}}} = c_{{2}^{\ 2^{\ 2}}} = 1^4 = 4~. \end{aligned} $$

   $$ \begin{aligned} &c_{k - 3} = c_3 = 0~,\\ &2 ^ {k - 3} = 2 ^ 1 = 2~,\\ &c_{{k-3}^{\ 2^{\ k-3}}} = c_{{1}^{\ 2^{\ k-3}}} = c_{{1}^{\ 2^{\ 1}}} = 0^2 = 0~. \end{aligned} $$

   $$ \begin{aligned} &c_{k - 4} = c_0 = 0~,\\ &2 ^ {k - 4} = 2 ^ 0 = 0~,\\ &c_{{k-4}^{\ 2^{\ k-4}}} = c_{{0}^{\ 2^{\ k-4}}} = c_{{0}^{\ 2^{\ 0}}} = 0^0 = 0~. \end{aligned} $$

   四者相加为:$8 + 4 + 0 + 0 = 12$,正好为 $(b) _ {10}$ 的值。

   这样一来,第一个式子就可以理解了。

   让我们来理解第二个式子。

   因为:

   $(a)_{10} = 2$

   $c_{{k-1}^{\ 2^{\ k-1}}} = 8$

   $c_{{k-2}^{\ 2^{\ k-2}}} = 4$

   $c_{{k-3}^{\ 2^{\ k-3}}} = 0$

   $c_{{k-4}^{\ 2^{\ k-4}}} = 0$

   因为第三项和第四项的值为 $0$,故舍去。

   $a ^ 8 * a ^ 4 = 2 ^ 8 * 2 ^ 4 = 256 * 16 = 4096$

   这样一来,第一个公式和第二个公式我们就都搞懂了,这样有助于帮助我们理解快速幂。

   时间复杂度:

   因为 $k=\left\lfloor{\log_2(b+1)}\right\rfloor$,所以上面式子的乘积的项数不超过 $\left\lfloor{\log_2(b+1)}\right\rfloor$ 个。

   所以时间复杂度为:$O((n\ \log_2(x))^k)$。

   C++ 代码:

typedef long long LL;

int qmi(int a, int b, int p)
{
    int res = 1 % p;
    for (; b; b >>= 1)
    {
        if (b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
    }
    
    return res;
}

   代码具体的理解我们可以看看下图:

图
图 1:样例

                     

© 小时科技 保留一切权利