您好,欢迎来到钮旅网。
搜索
您的当前位置:首页快速乘与快速幂的区别

快速乘与快速幂的区别

来源:钮旅网

快速幂

LL kuaisumi(LL a,LL b,LL m)
{//节省的是时间复杂度,与空间复杂度和数值的关系不大;并不能解决数据过大问题
	if(b==0)
		return 1;
	if(b%2==1)//可以用b&1代替 &是位运算符 
		return a*kuaisucheng(a,b-1,m)%m;
	else{
	
		LL mul=kuaisucheng(a,b/2,m);
		return mul*mul%m; 
	}
}

快速乘

LL kuaisucheng(LL a,LL b,LL m)
{
//思想在以前发的文章中
	LL res=0;
	while(b)
	{
		if(b&1)
			res=(res+a)%m;
		a=(a+a)%m;
		b>>1;
	}
}

快速幂节省了时间复杂度,快速幂运用乘变加,既节省时间复杂度,也避免了数据的爆炸

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- niushuan.com 版权所有 赣ICP备2024042780号-2

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务