快速幂 a^b

快速幂

根据数学常识，每一个正整数可以唯一表示为若干指数不重复的 2 的次幂的和。

$_math_inline$3^{13} = 3^{(1101)_2} = 3^8 \cdot 3^4 \cdot 3^1$math_inline_$

也就是说，如果 b 在二进制表示下有 k 位，其中第 $_math_inline$i(0 \leq i < k)$math_inline_$ 位的数字是 $_math_inline$c_i$math_inline_$ ，那么

$_math_inline$b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+...+c_{0}2^{0}$math_inline_$

于是

$_math_inline$a^b=a^{c_{k-1}*2^{k-1}}*a^{c_{k-2}*2^{k-2}}*...*a^{c_0}*2^0$math_inline_$

因为 $_math_inline$k=\lceil\log_2{(b+1)}\rceil$math_inline_$ ，所以上式乘积的数量不多于 $_math_inline$\lceil\log_2{(b+1)}\rceil$math_inline_$ 个

又因为 $_math_inline$a^{2^i}=\left(a^{2^{i-1}}\right)^2$math_inline_$ ，所以很容易通过 k 次递推求出每个乘积项，当 $_math_inline$c_i=1$math_inline_$ 时，把该乘积项累积到答案中

因此为了计算 $_math_inline$3^{13}$math_inline_$ ，我们只需要将对应二进制位为 1 的整系数幂乘起来就行了

$_math_inline$13 = (1101)_2$math_inline_$ $_math_inline$3^{13} = 6561 \cdot 81 \cdot 3 = 1594323$math_inline_$ $_math_inline$\begin{align} 3^1 &= 3 \\ 3^2 &= \left(3^1\right)^2 = 3^2 = 9 \\ 3^4 &= \left(3^2\right)^2 = 9^2 = 81 \\ 3^8 &= \left(3^4\right)^2 = 81^2 = 6561 \end{align}$math_inline_$

Code

Code 1

1LL quick_pow(LL a, LL b, LL p) {
2    a %= p;
3    LL res = 1 % p;
4    for (; b; b >>= 1) {
5        if (b & 1) res = res * a % p;
6        a = a * a % p;
7    }
8    return res;
9}

Problem

a^b