【算法笔记】快速幂

其实写这篇文章的主要目的是练习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} $$

快速幂代码如下：

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)

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

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;
}