快速乘取模＋快速幂取模 - che027

快速乘取模＋快速幂取模

单个的快速乘取模和快速幂取模时间复杂度都为O(logN)
ll mul(ll a,ll b)
{
    ll ans=0;
    while(b)
    {
        if(b&1)ans=(ans+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return ans;
}
ll poww(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)ans=mul(ans,a);
        a=mul(a,a);
        b>>=1;
    }
    return ans;
}