快速幂与快速乘小结

题目链接:牛客网小白月赛12-B题

题目描述:

链接:https://ac.nowcoder.com/acm/contest/392/B
来源:牛客网
找到了心仪的小姐姐月月后,华华很高兴的和她聊着天。然而月月的作业很多,不能继续陪华华聊天了。华华为了尽快和月月继续聊天,就提出帮她做一部分作业。
月月的其中一项作业是:给定正整数A、B、P,求$A^{B}modP$的值。华华觉得这实在是毫无意义,所以决定写一个程序来做。但是华华并不会写程序,所以这个任务就交给你了。
因为月月的作业很多,所以有T组询问。
输入描述:
第一行一个正整数T表示测试数据组数。
接下来T行,每行三个正整数A、B、P,含义如上文。
输出描述:
输出T行,每行一个非负整数表示答案。
示例1
输入
2
2 5 10
57284938291657 827493857294857 384729583748273
输出
2
18924650048745

快速幂:

此题同时用到了快速幂和快速乘,所以在此总结一下;

首先是快速幂是用于快速求解$A^{B}modP$这类问题
对于 $A^{B}modP$ 这类问题,朴素的做法是

1
2
3
int tmp = 1;
for(int i = 0; i < B; i++)
tmp = (tmp * A) % MOD;

按照题意要求模拟$A^{B}$过程中每次取余即可;这样做,虽然结果是对的,但是效率不够高.时间复杂度为O(B);
那这个过程能不能加速呢? 是可以的,就是我们今天要说的这个快速幂;
那他的原理是咋样的呢?
如果B是偶数 那么有 $A^{B}modP$ 等价于 $A^{2^{\frac{B}{2}}}modP$
如果B是奇数 那么有 $A^{B}modP$ 等价于 $A * A^{2^{\frac{B-1}{2}}}modP$

举个例子
$3^{5}mod4$
第一步:
初始化最终结果tmp = 1
我们发现5是奇数 所以可以将其拆分为 $3 \times 3^{2^{\frac{5-1}{2}}}modP$
显然 我们可以计算出
tmp = tmp $\times$ A, A = A $\times$ A
然后对B进行右移操作,即除以2然后向下取整,此时
A = 9, B = 2, tmp = 3,对剩下的部分继续快速幂
第二步:
我们发现没算的那个2是偶数 所以可以得出 $3^{2^{\frac{2}{2}}}modP$
显然 我们可以计算出 A = A $\times$ A,然后对B进行右移操作,即除以2然后向下取整,此时A = 81, B = 1, tmp = 3,对剩下的部分继续快速幂
第三步:
我们发现没算的那个1是奇数 所以可以得出 $3^{2^{\frac{1-1}{2}}}modP$
显然 我们可以计算出 tmp = tmp $\times$ A, A = A $\times$ A
然后对B进行右移操作,即除以2然后向下取整,此时A = 729, B = 0, tmp = 243;

第四步:
此时B为0,我们终止循环,返回tmp % mod即可;
显然,我们只是当B为奇数时把结果乘到tmp中,B为偶数时,我们只将A改变为其的平方即可;这样就可以加速运算;
我自己的pow_mod

1
2
3
4
5
6
7
8
9
10
11
12
13
#define long long long
long pow_mod(long a, long b, long mod)
{
long tmp = 1;
while(b)
{
if(b & 1)
tmp = ( (tmp % mod) * (a % mod) ) % mod;
a = ( (a % mod) * (a % mod) ) % mod;
b >>= 1;
}
return tmp;
}

快速乘

考虑到在做快速幂的时候 a $\times$ a可能会爆long long. 如果你说你要用Java或Python的大整数,那也可以,不过还是建议学一下快速乘;

举个例子:
20 $\times$ 11=20 $\times$ (1011)=20 $\times$ $2^{3}$ $\times$ 1 + 20 $\times$ $2^{2}$ $\times$ 0 + 20 $\times$ $2^{1}$ $\times$ 1 + 20 $\times$ $2^{0}$ $\times$ 1 = 160 + 40 + 20 = 220
我们可以看到,每次可以给a乘以2,若当前位为1则代表有贡献,对答案进行更新,否则就是没有贡献,跳过即可;这样我们每次做的都是 + 操作,所以不必担心爆long long;时间复杂度是O(logb)

1
2
3
4
5
6
7
8
9
10
11
12
13
#define long long long
long mul(long a, long b, long mod)
{
long tmp = 0;
while(b)
{
if(b & 1)
tmp = (tmp + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return tmp % mod;
}

题目代码:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;

#define long long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define MAX_N 200010

long mul(long a, long b, long mod)
{
long tmp = 0;
while(b)
{
if(b & 1)
tmp = (tmp + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return tmp % mod;
}

long pow_mod(long a, long b, long mod)
{
long tmp = 1;
while(b)
{
if(b & 1)
tmp = mul(tmp, a, mod);
a = mul(a, a, mod);
b >>= 1;
}
return tmp;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int t;
cin >> t;
while(t--)
{
long a, b, mod;
cin >> a >> b >> mod;
cout << pow_mod(a, b, mod) << endl;
}

return 0;
}
-------------本文结束,感谢您的阅读!-------------