快速乘法的说法来源于快速幂，因为两者的思想一致。快速幂是为了计算计算取模结果，的确是快的。而快速乘法主要是模数超过九次方时使用，因为两数相乘会longlong溢出，会比直接乘法慢，但是保证了正确性。所以说快速乘法并不快，想要比正常乘法快也是不现实的，快速乘法本来就是为了保证正确性而牺牲效率，自己实现了一遍乘法。要说快的话只能去和直接累加相比，就像快速幂比直接累乘取模快。

    1. // 类似快速幂
    2. // 时间复杂度log(n)
    4. // 写法1
    5. int qmul(int a, int b, int p){
    6.     int ret = 0;
    7.     while (b){
    8.         if (b & 1) ret = (ret + a) % p;
    9.         b >>= 1;
    10.         a = (a + a) % p;
    11.     }
    13.     return ret;
    14. }
    16. // 写法2
    17. typedef long long ll;
    19. ll qmul(ll a, ll b, ll p){
    20.     ll ret = 0;
    21.     for (; b; b >= 1){
    22.         if (b & 1) ret = (ret + a) % p;
    23.         a = a * 2 % p;
    24.     }
    26.     return ret;
    27. }