快速幂||取余运算

代码

代码(C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int quick_pow(int a,int n/*,int p*/)
{
long long base=a;
int ans=1;
while(n)
{
if(n&1)
{
ans*=base;
//ans%=p;
}
n>>=1;
base*=base;
//base%=p;
}
return ans;
}

分析

本题计算:

$ a^n \mod p $

首先观察$2^5=32$这个式子。

我们知道$5$的二进制为$101$。

我们还知道$32=2^4 \times 2^1$

再来看$2^7=128$,

我们知道$7$的二进制为$111$,

我们还知道$128=2^4 \times 2^2 \times 2^1$

以此类推,我们发现:

二进制 6 5 4 3 2 1
$a^{32}$ $a^{16}$ $a^8$ $a^4$ $a^2$ $a^1$

所以:

假如我们要计算$a^n$,只需要把$n$分解成二进制,将“$1$”位对应的$a^k$相乘即可

我们发现表格中$a^k=( a^{(k-1)} ) ^2$

所以表格中第$k$位的幂为$a^{2^{ ( k-1 ) }}$

再来看代码:

其中n&1代表检查n二进制最后一位是不是$1$;

n>>=1代表将n右移一位(等效于n/=2),用于检查下一位是不是$1$

如果最后一位是$1$,那么答案乘上base

其中base记录了表格第二行的数据,以每次自乘一次更新

如果要取模,则再baseans每次进行运算时$\mod p$。

最后,在n==0,也就是n的每一位都检查完毕后跳出循环,返回答案。

时间复杂度

$$ T(N) = O(\log N) $$

参考文献

  1. 快速幂和取余运算 - 学委的博客