今天学了倍增,终于把非递归快速幂看懂了。
还是把$a^n$拆分成二进制形式。
例如:
$$
a^{10} = a^{(1010) _ 2} = a^{1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0} = a^{1 * 2^3} * a^{1 * 2^1}
$$
我们可以通过倍增的方法先计算$\mod p$意义下的$a^1$,$a^2$,$a^4$,$a^8$,$a^{16}$,$a^{32}$,再把它们根据$b$的二进制拆分乘起来。
下面请看代码实现:
1 | // a ^ b % p |