『算法-ACM 竞赛-数学-数论』快速乘法+快速幂

1.快速幂（快速模幂）
① 求 a^b:

int pow(int a, int k)  {
    int ans = 1;
    while(k)  {
        if(k &1)  ans *= a;   //判断奇偶只用判断最后一位比取模快
        a *= a;
        k >>=1;		//比除法快多了
    }
    return ans;
}
②求a^b%p

int pow_mod(int a, int k,int mod)  {
     int ans = 1%mod;
     while(k)  {
         if(k &1)  ans =(long long) ans*a%mod;  //防止在对P取模前溢出
         a = (long long)a*a%mod;
         k >>=1;  //比除法快多了
     }
     return ans;
 }
例题：BZOJ1008
2.快速乘法
方法①

long long quickMul(long long a,long long b,long long mod)
{
    long long ans=0;
    while(b){
        if(b&1) ans=(ans+a)%mod;
        a=(a+a)%mod;  //（计算机加法比乘法快，a+a比a*2快）
        b>>=1;
    }
    return ans;
}

方法②：高效算法

long long quickMul(long long a,long long b,long long mod)
{
    a%=mod;
    b%=mod;
    long long  ans=0;
    while(b){
        if(b&1){
            ans+=a;
            if(ans>=mod)
               ans-=mod;
        }
        b>>=1;
        a<<=1;
        if(a>=mod)  a-=mod;
    }
   return ans;
}

方法③：使用long double优化版

long long quickMul(long long a,long long b,long long mod)
{
    a%=mod;
    b%=mod;
    long long c=(long double) a*b/mod;
    long long ans=a*b-c*mod;
    if(ans<0) ans+=mod;
    else if(ans>=mod) ans-=mod;
    return ans
  }