快速幂取模

1.先了解两个公式：

a^b mod c=[(a mod c)^b] mod c

(a*b)mod c = [(a mod c)*(b mod c)]mod c

然后求a^b的快速幂

（1）b是偶数

a^b mod c=((a)^2)^(b/2))mod c,记k=a^2 mod c,求k^(b/2) mod c.

(2)b是奇数

a^b mod c = ((a^2)^(b/2)*a)mod c,记k=a^2mod c,求（（k)^(b/2) mod c *a)mod c.

算法实现

1.循环实现

int Pow_mod(int a,int b,int c)
{
    int ans=1;
    a%=c;
    while(b>0)
    {
        if(b&1) ans=(ans*a)%c;//判断b是否为奇数
        b/=2;
        a=(a*a)%c;
    }
}

2.递归实现

int pow_mod(int a,int b,int c)
{
    if(b==0) return 1;
    int x=pow_mod(a,b/2,c);
    long long ans = (long long)x*x%c;
    if(b&1) ans = ans*a%c;
    return (int) ans;
}

快速乘法 a*b 实际上就是b个a 相加

long long pow_multiply(long long a,long long b)
{ 
   long long ans=0;
   while(b) 
   {
      if(b&1) ans=(ans+a)%mod;
      b>>=1;//b/2
     a =(a+a)%mod;
   }
   return ans;
}