快速幂模板：

typedef long long LL;LL fast_pow(LL a, LL n, LL mod)//快速幂 {    LL ans = 1;    while (n)    {        if (n & 1)            ans = ans*a%mod;        a = a*a%mod;        n >>= 1;    }    return ans;}

如果你是按照二进制来理解快速幂的 那么快速乘也一定很好理解

模板如下：

LL fast_multi(LL m, LL n, LL mod)//快速乘法 {    LL ans = 0;//注意初始化是0，不是1     while (n)    {        if (n & 1)           {             ans += m;             ans %= mod;           }        m = (m + m) % mod;//和快速幂一样，只不过这里是加         n >>= 1;    }    return ans;}

有了快速乘 那么就可以得到改进后的快速幂 可以防爆

LL fast_pow(LL a, LL n, LL mod)//快速幂 {    LL ans = 1;    while (n)    {        if (n & 1)            ans = fast_multi(ans, a, mod);//不能直接乘         a = fast_multi(a, a, mod);        ans %= mod;        a %= mod;        n >>= 1;    }    return ans;}

防爆乘一并放出：

LL mult_mod(LL a, LL b, LL m){    ll c = a*b-(ll)((long double)a*b/m+0.5)*m;    return c<0 ? c+m : c;  //就是算的a*b%m;}