算法模板

常用算法的模板

数论

快速幂

ll fastPower(ll base, ll power, ll mod) {
    ll result = 1;
    while (power > 0) {
        if (power & 1) {
            result = result * base % mod;
        }
        power >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

GCD

直接用STL库里的__gcd()就好了

__gcd()

EXGCD

// 解ax + by = gcd(a, b)的x和y
// 求最小非负整数解的话外面加一句
// x = (x % b + b) % b;
void exgcd(ll a_, ll b_, ll &d_, ll &x_, ll &y_) {
    if (!b_) {
        d_ = a_, x_ = 1, y_ = 0;
    } else {
        exgcd(b_, a_ % b_, d_, y_, x_);
        y_ -= x_ * (a_ / b_);
    }
}

通过EXGCD求逆元

// 返回 a_^(-1) mod n_
ll invMul(ll a_, ll n_) {
    ll d_, x_, y_;
    exgcd(a_, n_, d_, x_, y_);
    return d_ == 1 ? (x_ + n_) % n_ : -1;
}

通过递推的方式求逆元

ll fastPower(ll base, ll power, ll mod) {
    ll result = 1;
    while (power > 0) {
        if (power & 1) {
            result = result * base % mod;
        }
        power >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

const int MOD=7; //替换成对应的MOD值

//阶乘和逆元
ll fac[200010];        //阶乘
ll inv[200010];        //逆元 
void getfac()
{
    fac[0] = inv[0] = 1;
    for (int i = 1 ; i <= 200000 ; i++)
    {
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = fastPower(fac[i], MOD-2, MOD);        
        //表示i的阶乘的逆元 
    }
}
//组合数
inline ll getC(ll n,ll m)//C(n,m) = n!/((n-m)!*m!) % MOD
{
    return fac[n] * inv[n-m] % MOD * inv[m] % MOD;
}

//当 n，m 过大时，可以用Lucas定理降数据
inline ll Lucas(ll n,ll m)
{
    if(n < MOD && m < MOD) return getC(n, m);
    return Lucas(n/MOD, m/MOD) * getC(n%MOD, m%MOD)%MOD;
}

//排列数
inline ll getA(ll n,ll m) //A(n,m) = n!/(n-m)! % MOD
{
	return n * inv[n-m] % MOD;
}

中国剩余定理

ll CRT(ll n_, vector< ll > &a_, vector< ll > &m_) {
    ll M_ = 1, d_, y_, x_ = 0;
    for (int i = 1; i <= n_; i++)
        M_ *= m_[i];
    for (int i = 1; i <= n_; i++) {
        ll w = M_ / m_[i];
        exgcd(m_[i], w, d_, d_, y_);
        x_ = (x_ + y_ * w * a_[i]) % M_;
    }
    return (x_ + M_) % M_;
}

BSGS

// y^x 同余 z (mod p)的最小非负整数解x
ll bsgs(ll y, ll z, ll p) {
    map< ll, ll > M;
    ll m = sqrt(p) + 1;
    y %= p;
    z %= p;

    ll cnt = 0, sum = 1;
    for (int d = gcd(y, p); d != 1; d = gcd(y, p)) {
        if (z % d)
            return -LLONG_MAX;
        ++cnt, z /= d, p /= d, sum = sum * y / d % p;
        if (z == sum)
            return cnt;
    }

    for (ll i = 0, zy_i = z; i <= m; i++, zy_i = zy_i * y % p)
        M[zy_i] = i;

    for (ll i = 1, y_m = fastPower(y, m, p), y_mi = y_m; i <= m; i++, y_mi = y_mi * y_m % p)
        if (M.count(y_mi))
            return i * m - M[y_mi];

    return -LLONG_MAX;
}

分解质因数/线性筛

struct Prime {
    int n;
    vector<int> prime, nxt;
    vector<bool> isp;
    
    Prime(int n) : n(n+1), prime(1), nxt(n+1), isp(n+1,1) { calc(); }

    void calc() {
        isp[1] = 0;
        for (int i = 2;i <= n; ++i) {
            if (isp[i]) prime.push_back(i), nxt[i] = i;
            for (int j = 1;j < sz(prime) && i*prime[j] <= n; ++j) {
                isp[i*prime[j]] = 0;
                nxt[i*prime[j]] = prime[j];
                if (i % prime[j] == 0) break;
            }
        }
    }
    
    vector<pair<ll,int>> factorize(ll x) { 
        vector<pair<ll,int>> ret;
        while (x != 1) {
            int p = nxt[x];
            if (ret.empty() || ret.back().first != p) ret.push_back({p, 1});
            else ret.back().second++;
            x /= p;
        }
        return ret;
    }
};

单个质因数分解

vector<pair<ll, ll>> factorize(ll x) {//唯一分解定理
    vector<pair<ll, ll>> ret;
    for (int i = 2; (ll)i*i <= x; ++i) if (x % i == 0) {
        ret.push_back({i, 0});
        while (x % i == 0) x /= i, ret.back().second++;
    }
    if (x > 1) ret.push_back({x, 1});
    return ret;
}