首页 > itarticle > 快速乘（龟速乘）学习笔记

快速乘（龟速乘）学习笔记

admin 11月 10, 2020 0

要解决的问题

给定 $a,b,$ 求 $a*bmod c.$
如果用常规的乘法运算和取余运算，可能会爆$int$或者爆$long long$.
所以有什么好的方法呢？

模型构建

和快速幂一样的思路，用分治。

模板代码（快速乘+快速乘实现的快速幂）

typedef long long ll;
ll (ll a,ll b,ll mod) {
   
 ll ans=0;
    while(b) {
      if(b&1) ans+=a;
     a=(a+a)%mod;
     a%=mod;
      ans%=mod;
        b>>=1;
 }
    return ans;
} 
ll qpow(ll a,ll b,ll mod) {
 //a^b%mod
   ll ans=1;
    while(b) {
      if(b&1) ans=qmul(ans,a,mod);
        a=qmul(a,a,mod);
     ans%=mod;
        a%=mod;
      b>>=1;
 }
    return ans;
}