【算法笔记】快速幂

【算法笔记】快速幂

其实写这篇文章的主要目的是练习LATEX(大雾)

朴素地计算幂的方法就是计算出$b$个$a$的乘积,即
$$ \prod_{i=1}^b a=\underbrace{a \times a \times a \times \dots \times a}_b $$
(因为这篇文章主要介绍快速幂,代码就不贴了)

但是很明显,如果用这个算法去计算$2^{100000000000000}$,那么一定会T飞,原因很简单:
这个算法的时间复杂度是$O(n)$,对于计算幂这样频繁的操作来说代价太大了。

于是,我们就有了快速幂。

快速幂,又称平方求幂法,是一种基于分治思想在 $O(logn)$ 的时间复杂度内求幂的方法。

首先,一个显而易见的事实是:
$$ n^a \times n^b=n^{a+b} $$

于是当n为奇数有:
$$ a^b=a^{ \lfloor\frac{n}{2}\rfloor + \lfloor\frac{n}{2}\rfloor + 1} $$
当n为偶数有:
$$ a^b=a^{ \frac{n}{2} + \frac{n}{2}} $$
所以
$$ a^b=\begin{cases}
a &b=1 \cr
a^{\lfloor\frac{n}{2}\rfloor} \times a^{\lfloor\frac{n}{2}\rfloor} \times a &b \nmid 2 \cr
a^{\frac{n}{2}} \times a^{\frac{n}{2}} &b\mid 2
\end{cases} $$

快速幂代码如下:

1
2
3
4
5
6
int ksm(int a,int b)
{
if(b==1) return a;
else if(b%2==1) return ksm(a,b/2)*ksm(a,b/2)*a;
else return ksm(a,b/2)*ksm(a,b/2)
}

快速幂取模

有时候,因为求出的幂太大,我们不仅想要求出幂,还想求出幂对一个指定的数取模的结果,这时候,我们就要利用余数的可乘性,即

(a mod m) * (b mod m) = (a*b) mod m

(抱歉这里用不了LATEX)

方法很简单,在快速幂计算时的每一处乘法加上取模就可以了
代码如下:

1
2
3
4
5
6
int ksm(int a,int b,int mod)
{
if(b==1) return a;
else if(b%2==1) return (((ksm(a,b/2,mod)*(ksm(a,b/2,mod))%mod*a)%mod;
else return ((ksm(a,b/2,mod)*(ksm(a,b/2,mod))%mod;
}
文章作者: 1379号监听员
文章链接: https://listener1379.site/2019/【算法笔记】快速幂/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 1379号监听站
支付宝打赏
微信打赏