快速幂和快速乘

1.1快速幂

ll quick_pow(ll a,ll b,ll mod) {
    ll res=1;
    a%=mod;
    while(b) {
        if(b&1)(res*=a)%=mod;
        (a*=a)%=mod;b>>=1;
    }
    return res%mod;//mod==1
}

1.2快速乘

ll quick_mul(ll a,ll b,ll mod) {
    ll res=0;
    while(b) {
        if(b&1)
            (res+=a)%=mod;
        (a<<=1)%=mod;//注意此处会不会溢出
        b>>=1;
    }
    return res;
}

typedef unsigned long long ull;//浮点运算不太可靠
ll quick_mul(ll a,ll b,ll mod) {
    ll c=(long double)a/mod*b;//a*b/mod
    ll res=(ull)a*b-(ull)c*mod;//a*b-a*b/mod*mod
    return (res+mod)%mod;
}