快速幂

贡献者：待更新

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