【C++/算法】快速幂算法详解

1、数字溢出怎么办？

使用取模运算性质：

(a * b) % p = [(a % p) * (b % p)] % p

2、证明模运算性质的过程中为什么要设定？

a = k1 * p + q1

b = k2 * p + q2

这里我自己补充下作者的证明。

为了证明 (a * b) % p = (a % p * b % p )% p，

我们需要先证明 a % p * b % p 的值在模 p 的意义下等于 a * b 的值在模 p 的意义下。

设 a mod p = q1，b mod p = q2，

那么：

a = k1 * p + q1

b = k2 * p + q2

其中 k1 和 k2 是任意整数。

所以，

a*b = (k1*k2*p + k1*q2 + k2*q1)*p + q1*q2

然后取模：

(a * b) % p = (q1 * q2) % p

其中：

(k1*k2*p + k1*q2 + k2*q1)*p 为 0，被直接消去了。因为该项是 p 的倍数。

又：

a = k1 * p + q1

b = k2 * p + q2

则：

a % p = q1

b % p = q2

进而：

q1 * q2 = a % p * b % p

所以在模 p 的意义下：

(a * b) % p = [(a % p) * (b % p)] % p

3、快速幂原理？

底数平方，指数除以2。

将 O(n) 的时间复杂度，转换成 O(log) 级别的时间复杂度。