快速乘法

快速乘的名字是从快速幂抄过来的,事实上它比直接乘要慢。

思路和快速幂一样,对于 k×xk \times x ,可将其视为 k2×x+k2×x\frac{k}{2} \times x + \frac{k}{2} \times x ,若 kk 为奇数,则再加个 xx

1
2
3
4
5
6
7
int fastTimes(int x, int k, int p) {
if(k == 0) return 0;
int z = fastTimes(x, k >> 1, p);
z = (z + z) % p;
if(k % 2 == 1) z = (z + x) % p;
return z;
}