快速乘

引自2009国家集训队论文：骆可强：《论程序底层优化的一些方法与技巧》 

 

代码：//挺迷的，不知道为什么，好用就是了

ll fast_mult(ll a,ll b,ll mod)
{
    return (a*b-(ll)((long double)a/mod*b)*mod+mod)%mod;
}//ll为long long

快速幂

ll fpow(ll a,ll b,ll c)
{
    a%=c;
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%c;
        a=a*a%c;
        b>>=1;
    }
    return ans%c;
}

慢速乘（快速加）

ll fmult(ll a,ll b,ll c)
{
    a%=c;
    ll ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%c;
        a=(a+a)%c;
        b>>=1;
    }
    return ans%c;
}