快速乘法模板

2019-04-13 16:29发布

站内文章 / 模拟电子
16196 0 1147
快速乘法使用二进制将乘法转化为加法，既加快可以加快运算速度，又可以防止直接相乘之后溢出 简单的写法： ll quickMul(ll a,ll b,ll mod) { ll res=0; while(b){ if(b&1) res=(res+a)%mod; a=(a+a)%mod; b>>=1; } return res; } 更快更高效的写法： ll mul(ll a,ll b,ll mod) { a%=mod; b%=mod; ll res=0; while(b){ if(b&1){ res+=a; if(res>=mod) res-=mod; } b>>=1; a<<=1; if(a>=mod) a-=mod; } return res; } 利用快速乘法优化的快速幂： ll mul(ll a,ll b,ll mod) { a%=mod; b%=mod; ll res=0; while(b){ if(b&1){ //printf("%lld %lld %lld ",a,b,res); res+=a; if(res>=mod) res-=mod; } b>>=1; a<<=1; if(a>=mod) a-=mod; } return res; } ll quickPow(ll a,ll b,ll m) { ll res=1; while(b){ if(b&1) res=mul(res,a,m); a=mul(a,a,m); b>>=1; } return res; }  

热门文章