背景

做乘法运算往往会溢出，即使用long long类型也拯救不了。而且，在计算机中做加法运算会比乘法快得多。因此需要寻找一种能高效完成乘法运算且不会溢出的算法，这就是快速乘算法。
快速乘与快速幂原理相似，也是将运算转换为二进制处理：
以$5 \cdot 11 $ 为例： $5 \cdot 11 = 5 \cdot (1011)_2 = 5 \cdot (1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0) = 5 \cdot 2^3 + 5 \cdot 2^1 + 5\cdot 2^0$
可以看出，每次查看11的一个二进制位，且把5翻倍就可以了。

模板：

//a * b
ll ksc(ll a, ll b, ll p) {
    ll res = 0;
    while(b) { //若b是负数，会在左边无限补1，导致死循环
        if(b & 1) res = (ans + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return (res%p+p)%p;//a可能是负数，经常需要把res转为模p下的最小正解
}

解释：
1、必须保证b是大于0的，如果b是负数，根据二进制规则，负数左边会无限补1，就无法结束循环了
2、最后的res，由于a可能是负数，要想返回最小正解的res，就得模一下。

如果快速乘的两个数a，b都不能保证为正数，或者说a，b都可能是负数，确定不了

解决办法很简单，提前做一下判断，把b的负号移到a上面去

ll ksc(ll a, ll b, ll p) {
    if(b<0){
        a=-a,b=-b; //a*b时，a，b同时加负号，乘积不变
    }
    ll res = 0;
    while(b) {
        if(b & 1) res = (ans + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return (res%p+p)%p;//a可能是负数
}