快速幂与快速乘

Varuxn · 2021-03-13 08:33:35 · 个人记录

快速幂

int ksm(int a,int b,int mod)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=a*ans%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

快速乘

ll mul(ll x, ll y)
{
    ll L=x*(y>>25)%mod*(1<<25)%mod;
    ll R=x*(y&((1<<25)-1))%mod;
    return (L+R)%mod;
}