【题解提供者】吴立强
解法一
思路
【快速幂】算法模板题。
面对 a b m o d p a^b\mod p abmodp 这个结构,并没有什么显而易见的切入点,直接求必然超时 O ( b ) O(b) O(b)。
而快速幂算法是先将 b b b 二进制分解(假设 b b b 的二进制表示为 b 29 b 28 b 27 . . . b 2 b 1 b 0 b_{29}b_{28}b_{27}...b_2b_1b_0 b29b28b27...b2b1b0),那么就有:
a b = ∏ i = 0 29 ( b i × a 2 i ) a^b = \prod _{i=0}^{29}(b_i\times a^{2^i}) ab=∏i=029(bi×a2i)
由于乘法取模可以对乘法各部分先取模,所以有:
a b m o d p = ( ∏ i = 0 29 ( ( b i × a 2 i ) m o d p ) ) m o d p a^b\mod p = (\prod _{i=0}^{29}((b_i\times a^{2^i})\mod p))\mod p abmodp=(∏i=029((bi×a2i)modp))modp
通过上面的式子,我们将原本的 a b a^b ab 经由 b b b 的二进制拆分转化成了 30 个(因为 2 30 > 1 0 9 2^{30} > 10^9 230>109)子结构的乘积,如果可以较为快速的处理出这 30 个子结构的值,那么原式的值也就求出来了。
b b b 的二进制拆分并不难,而 a a a 则需依次求解出 a 1 , a 2 , a 4 , a 8 . . . a^1,a^2,a^4,a^8... a1,a2,a4,a8...,注意到其每一项都是前一项的平方,通过递推也就可以做到依次求解了。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll a, b, p; cin >> a >> b >> p;
ll ans = 1;
/// 二进制拆解 b
while(b) {
/// 当前 b 的最后一位是 1
if(b & 1) ans = ans * a % p;
/// 将 a 平方
a = a * a % p;
/// 移除 b 的最后一位
b >>= 1;
}
/// 注意,当 b 为 0 时 while 循环内部语句不会执行
/// 此时 ans 为 1,如果 p 也为 1,那么答案应该是 0
/// 故输出前一定要将结果再模 p
cout << ans % p;
return 0;
}
算法分析
本算法的时间复杂度为 O ( log ( b ) ) O(\log(b)) O(log(b))。