快速幂
问题
求出$a^b\mod c$的值,其中a,b,c是整数,且$0<a,c<10^9$,$0<b<10^{18}$
算法设计
暴力算法
考虑用循环直接求出$a^b$的值,最后对$c$取模。
1 |
|
这个代码其实有两个缺陷。
- 时间复杂度为$O(b)$,即要进行$10^{18}$次运算,一般情况下计算机在1s内无法完成。
- ans会超过long long范围。
下面对其进行优化。我们来看看取模的性质:
$(ab)\mod c=((a\mod c)(b\mod c))\mod c$
所以我们可以在每一次乘$a$的时候都对$c$取模,即
1 |
|
这样我们就解决了缺陷2。但是时间复杂度并没有优化,还有没有别的办法呢?
快速幂算法
我们首先考虑一下手算$3^{10}$,$3^{10}=(3^2)^5=9^5=99^4=981^2=9*(81^2)^1$,很容易发现规律。而且,这个算法时间复杂度为$O(log_2b)$,时间大大减少。
1 |
|
补充:费马小定理
若$p$为素数,$a$为正整数,且$p,a$互质。则有$a^{p-1}=1\mod p$。
快速幂
https://serendipity565.github.io/posts/bfd6319e77d8/