快速幂

                     

贡献者: 待更新

   快速幂算法和前缀和算法的作用一样,都是优化某些操作的时间复杂度。所以快速幂算法就是可以很快速的:求 $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:样例

致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元,我们一周就能脱离亏损, 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利