快速乘模板(以取模)

快速乘是为了防止在乘的时候溢出(即使使用了同余模定理,还是会溢出),但这种情况比较少见,但还是有的,所以会用到快速乘

LL mult(LL A,LL B)
{
    LL z = 0;
    if (B == 0) return z;
    z = mult(A,B >> 1);
    z = (z << 1) % mod;
    if (B & 1) z = (z + A) %mod;
    return z;
}
原文地址:https://www.cnblogs.com/lalalatianlalu/p/7450520.html