程序设计竞赛模板之快速幂

代码如下:

long long mod_pow(long long x,long long n,long long mod)
{
  long long res=1;
  while (n>0)
  {
    if(n & 1)res=res*x%mod;
    x=x*x%mod;
    n>>=1;
  }
  return res;
}

原理解析:

X^4=(X^2)^2

所以X^7=X^(1+2+4)=X * X^2 *X^4

快速幂就是利用这个原理

同时,如果需要对P取余

设a1=c1*p+d1,则

a1^2=(c1*p)^2+2*c1*d1*p+d1^2

所以(a1%p)^2=a1^2%p

不影响结果

发表评论

电子邮件地址不会被公开。 必填项已用*标注