快速幂与快速乘模板

文章目录

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