【模板】快速幂

很简单

举个例子,算$base^{11}$

$11$转化为$2$进制是$1011$,所以我们可以把$base^{11}$转化为$base^{2^0+2^1+2^3}$,即$base^{2^0} \times base^{2^1} \times base^{2^3}$

于是从右往左处理$1011​$的每一位(设这是第$i​$位),如果是$1​$就给结果乘上$base^{2^{i-1}}​$

那么这个$base​$的二的次幂怎么处理?

我们用一个很简单的办法。做$1011​$的每一位时都让当前的$base自​$乘,然后你会发现在第$i​$位时$base​$变成了$base^{2^{i-1}}​$,就很好

上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
typedef long long LL;
using namespace std;
LL b,p,k;

inline LL ksm(LL base,LL po,LL modnum)
{
register LL res=1;
while (po)
{
if (po&1)
res=res*base%modnum;
base=base*base%modnum;
po>>=1;
}
return res%modnum;
}

int main()
{
scanf("%lld%lld%lld",&b,&p,&k);
printf("%lld^%lld mod %lld=%lld\n",b,p,k,ksm(b,p,k));
return 0;
}
-------------本文结束,感谢阅读-------------
0%