快速乘_c/c++
快速乘的使用主要是这种情形：要计算(a * b) % p时，发现a * b爆 long long 了，而a, b, p没有爆 long long
快速乘的原理:
比如当我们需要要计算3 * 21，我们可以拆成：3*( 1 + 4 + 16 )，也就是将21拆成2的倍数累加
想要得到括号里的累加值，我们可以通过二进制运算
例中21的二进制为00010101，当位为1时乘上相应权值相加
然后用去括号，就得出3 * 21 = 3 * 1 + 3 * 4 + 3 * 16
1 //快速乘模板 2 3 long long int qmuti(long long int a, long long int b, long long int p){ 4 long long int res = 0; 5 while(b){ 6 if(b & 1) res = (res+a)%p; 7 a= (a+a)%p; 8 b >>= 1; 9 } 10 return res; 11 }