使用巴雷特模乘的模意义数模板

hikkio / 2023-08-31 / 原文

对不定模数取模时，取模的效率非常低，因为缺少编译器对取模做的基本优化。

我们手动对取模做优化，优化效果非常显著。

#include <bits/stdc++.h>
using namespace std;
namespace BRT
{
    typedef long long ll;
    typedef __uint128_t u128;
    int MOD=1;
    u128 brt=(u128)1<<64;
    inline void fix(ll &val)
    {val=val-MOD*(brt*val>>64);while(val>=MOD)val-=MOD;}
    inline void fix(int &val){val=val<0?(val+MOD):(val>=MOD?val-MOD:val);}
    inline void setmod(int P){brt=((u128)1<<64)/P;MOD=P;}
    struct Modint{
        int val;
        static ll tmp;
        Modint(){val=0;}
        Modint(int V){fix(V);val=V;}
        Modint(ll V){fix(V);val=V;}
        inline Modint operator + (const Modint &rhs) const{return val+rhs.val;}
        inline Modint operator * (const Modint &rhs) const{return 1ll*val*rhs.val;}
        inline Modint operator - (const Modint &rhs) const{return val-rhs.val;}
        inline Modint operator - () const{return -val;}
        inline Modint& operator += (const Modint &rhs) {val+=rhs.val;fix(val);return *this;}
        inline Modint& operator *= (const Modint &rhs){tmp=1ll*val*rhs.val;fix(tmp);val=tmp;return *this;}
        inline Modint& operator -= (const Modint &rhs){val-=rhs.val;fix(val);return *this;}
        inline Modint operator + (int rhs) const{return val+rhs;}
        inline Modint operator + (ll rhs) const{return (ll)val+rhs;}
        inline Modint operator * (int rhs){return 1ll*val*rhs;}
        inline Modint operator * (ll rhs){fix(rhs);return 1ll*val*rhs;}
        inline Modint& operator += (int rhs){val+=rhs;fix(val);return *this;}
        inline Modint& operator += (ll rhs){fix(rhs);val+=rhs;fix(val);return *this;}
        inline Modint& operator *= (int rhs){fix(rhs);tmp=rhs*val;fix(tmp);val=tmp;return *this;}
        inline Modint& operator *= (ll rhs){fix(rhs);rhs=rhs*val;fix(rhs);val=rhs;return *this;}
    };
}
using mint=BRT::Modint;