快速幂

问题

求出$a^b\mod c$的值,其中a,b,c是整数,且$0<a,c<10^9$,$0<b<10^{18}$

算法设计

暴力算法

考虑用循环直接求出$a^b$的值,最后对$c$取模。

1
2
3
4
5
6
long long ans=1;
for (long long i=1;i<=b;i++)
{
ans*=a;
}
ans%=c;

这个代码其实有两个缺陷。

  1. 时间复杂度为$O(b)$,即要进行$10^{18}$次运算,一般情况下计算机在1s内无法完成。
  2. ans会超过long long范围。

下面对其进行优化。我们来看看取模的性质:

$(ab)\mod c=((a\mod c)(b\mod c))\mod c$

所以我们可以在每一次乘$a$的时候都对$c$取模,即

1
2
ans*=a;
ans%=c;

这样我们就解决了缺陷2。但是时间复杂度并没有优化,还有没有别的办法呢?

快速幂算法

我们首先考虑一下手算$3^{10}$,$3^{10}=(3^2)^5=9^5=99^4=981^2=9*(81^2)^1$,很容易发现规律。而且,这个算法时间复杂度为$O(log_2b)$,时间大大减少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef long long ll;
ll fast_pow(ll a,ll b,ll c)
{
ll ans=1;
a%=c;
while (b)//不能写成b>1,否则会出问题!!!
{
if (b%2==1)//可以用b&1进行更快的判断
{
ans=(ans*a)%c;
}
a=(a*a)%c;
b/=2;//可以用b>>=1来代替
}
return ans;
}

补充:费马小定理

若$p$为素数,$a$为正整数,且$p,a$互质。则有$a^{p-1}=1\mod p$。


快速幂
https://serendipity565.github.io/posts/bfd6319e77d8/
作者
Serendipity
发布于
2023年11月29日
许可协议
BY-SERENDIPITY565