一、题目背景
已知底数a,指数b,取模值mo
求ans = ab % mo
二、朴素算法
ans = 1,循环从 i 到 b ,每次将 ans = ans * a % mo
时间复杂度O(b)
void power(int a,int b,int mo) |
三、快速幂
当b为偶数时:ab=a(b/2)*2=(a2)b/2
当b为奇数时:ab=aab-1=a(a2)(b-1)/2
如 28=(22)4 27=2*(22)3
所以,我们可以如此迭代下去
210=(22)5=(22)*[(22)2]2
inline int mi(int a,int b) |