快速幂


快速幂

原理

一个数 k 均可以转换为二进制

10 (10)= 1010 (2)

10 = 2 + 8=2^1+2^3

经一般化处理可看出对于整数 a , b

a^b=a^x[0]+a^x[1]+a^[2]+···

如此可以大量减少乘法操作

代码实现

long long pow(long long a,long long b,long long p)	//a^b (mod p)
{
	long long ans=1;
	a%=p;//如果 a 大于 p,则必须进行取模
	for(; b; b>>=1)
	{
		if(b&1==1)	//此位为1 
        	ans*=(A%p);
		A=(A*A)%p;
	}
	return ans;
}

如果本文帮助到了你,帮我点个广告可以咩(o′┏▽┓`o)


评论
  目录