- 原理:使用二进制优化和快速幂思想相似
- 使用场景:一般使用在乘法模数系统中,加快计算速度并且防止溢出
- 代码:计算 (a*b)%mod 的结果
1 ll q_mult(ll a, ll b ,ll mod){ 2 ll ans = 0; 3 while(b){ 4 if(b&1) 5 ans = (ans + a)%mod; 6 a = (a<<1) % mod; 7 b>>=1; 8 } 9 return ans; 10 }
1 ll q_mult(ll a, ll b ,ll mod){ 2 ll ans = 0; 3 while(b){ 4 if(b&1) 5 ans = (ans + a)%mod; 6 a = (a<<1) % mod; 7 b>>=1; 8 } 9 return ans; 10 }