[AcWing89] 快速幂
要计算$3^7$,如果用$3×3×3×3×3×3×3$这种方法就要循环7次。那么有什么简单的方式呢?我们可以先预处理出$3^2$然后们就可以计算$9×9×9×3$。这样一来我们是不是就可以减少我们的循环次数呢?所以我们可以利用这种思想来解决这个问题。
$3^7 = 3^{(1+2+4)} = 3^1 × 3^2 × 3^4 = 3 × 9 × 27$
预处理出$3^1 × 3^2 × 3^4$这样就减少了循环次数,理解了上面之后。
我们单独来看这个7,我们知道7的二进制表示是$(7)_{2}=111$
- 如果我们的最后1位是1我们就要乘这个位权,也就是3
- 下一步我们需要更改我们的位权为9
- 同时右移这样变成11
- 下一步变成乘这个位权,也就是9
- 如此反复,直到b变成0
注:
*1ll
是为了防止溢出- 为什么每一步后面都要
%p
呢?这是我们利用了取余运算性质(a × b) % p = (a % p × b % p) % p
int qmi(int a,int b,int p)
{
int res = 1 % p;//这一步%p的目的是处理%1的情况
while(b)
{
if(b&1) res = res * 1ll * a % p;//如果我们的最后一位是1,那么就要更新res
//更新完毕后,我们需要更改一下我们的位权,比如我们第一个是×3,操作完之后就要变成×9
a = a * 1ll * a % p;
b >>= 1;//同时我们要把b右移
}
return res;
}
AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int qmi(int a,int b,int p)
{
int res = 1 % p;
while(b)
{
if(b&1) res = res * 1ll * a % p;
a = a * 1ll * a % p;
b >>= 1;
}
return res;
}
int main()
{
int a,b,p;
cin >> a >> b >> p;
cout << qmi(a,b,p);
return 0;
}
如有错误,欢迎各位uu指正