欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

快速幂

程序员文章站 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.变式

Acwing 90. 64位整数乘法
快速幂

#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;
}
相关标签: 快速幂