常用算法模版

今天学会在 https://godbolt.org/ 看汇编了。顺便卡了下常数，以及简单的（不是）压行。

快读

signed read() {
    signed num = 0, flag = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') flag = -1;
    for (; isdigit(ch); ch = getchar()) num = num * 10 + ch - '0';
    return num * flag;
}

若读数非负：

unsigned uread() {
    unsigned num = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) num = num * 10 + ch - '0', ch = getchar();
    return num;
}

卡常

template<typename _Tp> _Tp _max(const _Tp a, const _Tp b) { return a > b ? a : b; }
template<typename _Tp> _Tp _min(const _Tp a, const _Tp b) { return a < b ? a : b; }
template<typename _Tp> _Tp _abs(const _Tp x) { return x < 0 ? -x : x; }

快速幂

int qpow(int a, int b, int p) {
    int r = 1;
    for (; b; b >>= 1) (b & 1 ? r = r * a % p : true), a = a * a % p;
    return r;
}

欧几里得算法

int gcd(int a, int b) {
    while (b != 0) tie(a, b) = make_tuple(b, a % b);
    return a;
}

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) { x = 1, y = 0; return a; }
    int d = exgcd(b, a % b, y, x); y -= a / b * x;
    return d;
}

线性同余方程

若 \(n \mid \gcd(a, b)\)（有解），则可以删去第 \(3\) 行。

int lieu1(int a, int b) {
    int x, y, d = exgcd(a, b, x, y);
    if (d != 1) return -1;
    return (x % b + b) % b;
}

int lieu(int a, int b, int n) {
    int x, y, d = exgcd(a, b, x, y);
    if (n % d != 0) return -1;
    int t = b / d; return (x % t + t) % t;
}

乘法逆元

若 \(a \perp m\)（有解），则可以删去第 \(3\) 行。

int inv(int a, const int m) {
    int x, y, d = exgcd(a, m, x, y);
    if (d != 1) return 0;
    return (x % m + m) % m;
}

int inv(int a, const int m) {
    int x, y;
    exgcd(a, m, x, y);
    return (x % m + m) % m;
}

若有 \(m \in \mathbb P\)：

int inv(int a, const int p) {
    return qpow(a, p - 2, p);
}

求组合数

int comb(int a, int b, const int p) {
    return a < b ? 0 : fr[a] * sv[b] % p * sv[a - b] % p;
}

int lucas(int a, int b, const int p) {
    int r = 1;
    while (a && b) r = r * comb(a % p, b % p, p) % p, a /= p, b /= p;
    return r;
}

欧拉函数

int euler_phi2(int n) {
    int ans = n;
    for (int i = 2; i * i <= n; i++) { if (n % i == 0) {
        ans = ans / i * (i - 1);
        while (n % i == 0) n /= i;
    }}
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

扩展中国剩余定理合并

void merge(int &a1, int &m1, int a2, int m2) {
    int g = gcd(m1, m2), m = m1 / g * m2;
    int p, q; exgcd(m1 / g, m2 / g, p, q);
    p = p * m1 % m, p = p * ((a2 - a1) / g) % m;
    a1 = (a1 + p + m) % m, m1 = m;
}