快速幂

贡献者： 待更新

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

　　 数据范围：$0\le a,b\le {10}^9$，$1\le p\le {10}^9$。

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

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

　　 如果 $b$ 在二进制下有 $k$ 位，其中第 $i$（$0\le i\le k$）位的数字是 $c_i$，有：

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

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

　　 例子：求 $2^{12}mod1$ 的值，结果是 $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{array}{rl}& 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{array}$$

　　 $$\begin{array}{rl}& 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{array}$$

　　 $$\begin{array}{rl}& 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{array}$$

　　 $$\begin{array}{rl}& 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{array}$$

　　 四者相加为：$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\ast a^4=2^8\ast 2^4=256\ast 16=4096$

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

　　 时间复杂度：

　　 因为 $k=\lfloor {\log }_2(b+1)\rfloor$，所以上面式子的乘积的项数不超过 $\lfloor {\log }_2(b+1)\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;
}

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