• 欢迎光临~

快速幂的写法

开发技术 开发技术 2022-10-06 次浏览

1:

//注意事先请#define int long long,防止数据溢出
int f(int A,int B) { if(B==0) return 1; else if(B%2==0) { //如果B是偶数,则将其分成相等的两份 //于是可以先算出一份的结果,然后再乘上自身即可 //这样的写的话,递归调用的少了许多 int res=f(A,(B>>1)); return res*res%mod; } else { //与上同理,分成大小相差为1的两份 int res=f(A,(B>>1)); return A*res%mod*res%mod; } }

 

2:用while循环来写,更简单

 

 

 

3:如果是下面这样写,存在冗余。

int f(int a,int b)
{
 
	if(b==0)return 1;
	if(b==1) return a;
	if(b%2==0)
	    return f(a,b>>1)*f(a,b>>1)%mod;
	else
	    return a*f(a,b>>1)%mod*f(a,b>>1)%mod;
}

  

程序员灯塔
转载请注明原文链接:快速幂的写法
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com