一、题目背景

已知底数a,指数b,取模值mo

求ans = ab % mo

二、朴素算法

ans = 1,循环从 i 到 b ,每次将 ans = ans * a % mo

时间复杂度O(b)

void power(int a,int b,int mo)
{
int i;
ans=1;
for (i=1;i<=b;i++)
{
ans*=a;
ans%=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)
{
int ans=1;
a%=mo;
while (b)
{
if (b&1) ans=ans*a%mo;
b>>=1;
a=a*a%mo;
}
return ans;
}