[数论]快速幂 快速乘

使用方法

1. 直接调用 mult_mod(a,b,mod) 即可计算$$a \cdot b \mod MOD$$
2. 直接调用 pow_mod(x,n,mod)即可计算$$x^n \mod MOD$$

模板

ll mult_mod(ll a,ll b,ll mod)
{
    return (a*b-(ll)(a/(long double)mod*b+1e-3)*mod+mod)%mod;
}

ll pow_mod(ll x, ll n, ll mod)
{
    if(n==1)return x % mod;
    x%=mod;
    ll tmp=x;
    ll ret=1;
    while(n)
    {
        if(n&1)    ret=mult_mod(ret,tmp,mod);
        tmp=mult_mod(tmp,tmp,mod);
        n>>=1;
    }
    return ret;
}