# 模乘（解决乘法取模爆long long）

2024-10-06 22:58:45

模乘（解决乘法取模爆long long）

二进制思想，变乘法为多次加法，具体思想跟着代码手算一遍就理解了，挺简单的

ll qmul(ll a,ll b,ll m)

{

    ll ans=0;

    while(b){

        if(b&1) ans=(ans+a)%m;

        a=(a+a)%m;

        b=b>>1;

    }

    return ans;

}

//快速幂中的ans*a和a*a可能会爆LL，使用模乘解决

ll qpow(ll a,ll b,ll m)

{

    ll ans=1;

    while(b){

        if(b&1) ans=qmul(ans,a,m);

        a=qmul(a,a,m);

        b=b>>1;

    }

    return ans;

}

最新文章

热门文章