问题：
求 n*m % p 的值，其中0 <= n,m,p < 2^63。
大数？代码量太大，不值得，有没有更简单的方法?
一种思路：
俄式农夫乘法：
当n为偶数时： n * m=n/2 * 2m
当n为奇数时： n * m=(n-1)/2 * 2m + m
用位运算加速。无符号long long防溢出。
LL mult_mod(LL a , LL b , LL &p) {
if ( a < b ) a ^= b ^= a ^= b;
if ( b == 0 ) return 0;
LL t = mult_mod( (a << 1) % p , b >> 1 , p);
if ( b & 1 ) t += a;
return t % p;
} |
