快速乘法

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

思路和快速幂一样，对于 $k \times x$ ，可将其视为 $\frac{k}{2} \times x + \frac{k}{2} \times x$ ，若 $k$ 为奇数，则再加个 $x$ 。

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;
}