快速幂
程序员文章站
2022-06-04 12:24:40
...
快速幂
pow ( a , b );
太慢了QWQ
所以有了快速幂
1.基本思想是:
把指数分解成2的幂的积的形式
比如说,我们要求3 的 10次
我们就可以转化为3^2 * 3^8
;
怎么知道是2 和 8 呢??
这里我们需要知道二进制
10这个数在二进制中 是 1010;
我们发现在第2位和第4位是有数的,说明1010变成10进制就要*位数的权
这个时候问题就转化成了找二进制上是1的位数
相当于二进制的数位分离
写法:
while(p){
if(p & 1){
??????
p >>= 1;
}
显然与10进制数位分离一模一样
2.快速幂板子
#include<bits/stdc++.h>
using namespace std;
int x,y;
int quick(int n,int p){ //快速幂 板子
int ans = 1;int tmp = n;
while(p){
if(p & 1){
ans *= tmp;
}
tmp *= tmp;
p >>= 1;
}
return ans;
}
int main (){
scanf("%d %d",&x,&y);
printf("%d",quick(x,y));
return 0;
}
3.变式
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll x,y,r;
ll quick(ll n, ll p, ll r){
ll ans = 0; //因为这里是加法,所以一开始是0;
ll tmp = n;
while(p){ //如果没分完就继续循环
if(p & 1){//位运算--与
ans = (ans + tmp) % r;//每次都要%r//注意这里是加法
}
tmp = (tmp * 2) % r;
p >>= 1; //右移一位
}
return ans % r; //最后也要mod一下
}
int main (){
scanf("%lld %lld %lld",&x,&y,&r);
printf("%lld",quick(x,y,r));
return 0;
}
上一篇: 美团APP怎么查看公交乘车记录?