1. 数论

（1）质数

定义：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数（素数）。小于等于1的数既不是质数，也不是合数。

质数的判定–试除法

$O(\sqrt{n})$

bool is_prime(int u) {
    if (u < 2) return false;
    for (int i = 2; i <= u / i; i ++ ) {
        if (u % i == 0)
            return false;
    }
    return true;
}

分解质因数–试除法

$n$中最多只包含一个大于$\sqrt{n}$的质因子
最好$O(\log{n})$，最坏$O(\sqrt{n})$

void divide(int n) {
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            cout << i << ' ' << cnt << endl;
        }
    }
    if (n > 1) cout << n << ' ' << 1 << endl;
}

朴素筛质数

$O(n\log{n})$

int primes[N], cnt;
bool st[N];

void get_primes(int n) {
    for (int i = 2; i <= n; i ++ ) {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = 2 * i; j <= n; j += i)
            st[j] = true;
    }
}

埃氏筛质数

$O(n\log{\log{n}})$

void get_primes(int n) {
    for (int i = 2; i <= n; i ++ ) {
        if (!st[i]) {
            primes[cnt ++ ] = i;
            for (int j = i * 2; j <= n; j += i )
                st[j] = true;
        }
    }
}

线性筛质数

$O(n)$
$n$只会被最小的质因子筛掉，每个数只有一个最小质因子，所以每个数只会被筛一次
当$p_{j} \mid i$时，$p_{j}$一定是$i$的最小质因子，也一定是$p_{j} * i$的最小质因子
当$p_{j} \nmid i$时，$p_{j}$一定小于$i$的最小质因子，$p_{j}$也一定是$p_{j} * i$的最小质因子

void get_primes(int n) {
    for (int i = 2; i <= n; i ++ ) {
        if (!st[i]) primes[cnt ++ ] = i;
        // 从小到大枚举所有质数
        for (int j = 0; primes[j] <= n / i; j ++ ) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

（2）约数

求一个数的所有约数–试除法

$O(\sqrt{n} + klog(k))$, 其中$k$为约数的个数

vector<int> get_divisors(int n) {
    vector<int> ret;
    for (int i = 1; i <= n / i; i ++ ) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i != n / i) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}

约数个数和约数之和

$N = \prod_{i = 1}^{m}{p_{i}^{\alpha_{i}}}, 其中p_{i}为质数, 1 \leq \alpha_{i} \leq \log{n}$
$对于N的任意一个约数d, d = \prod_{i = 1}^{m}{p_{i}^{\beta_{i}}}, 0 \leq \beta_{i} \leq \alpha_{i}$
对于质因子$p_{i}$总共有$(1 + \alpha_{i})$种选法
约数个数为：$\prod_{i = 1}^{m}{(1 + \alpha_{i})}$
约数之和为：$\prod_{i = 1}^{m}{\sum_{j = 0}^{\alpha_{i}}{p_{i}^{j}}}$

欧几里得算法（辗转相除法）求最大公约数

已知$d \mid a, d \mid b \implies d \mid (ax + by)$，则$(a, b) = (b, a \; mod \; b)$
$a \; mod \; b = a - \lfloor \frac{a}{b} \rfloor \; b = a - cb$

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

（3）欧拉函数

欧拉函数（求$n$的欧拉函数是多少）

定义：$1$ ~ $N$中与$N$互质的数的个数被称为欧拉函数，记为$\phi(N)$
$N = p_{1}^{a_{1}}p_{2}^{a_{2}} \cdots p_{m}^{a_{m}}, 则\phi(N) = N * \frac{p_{1} - 1}{p_{1}} * \frac{p_{2} - 1}{p_{2}} * \cdots * \frac{p_{m} - 1}{p_{m}}$
证明：（容斥原理）
1. 去掉$p_{i} (i \in [1, m])$的倍数，
2. 加上所有$p_{i} * p_{j} (i, j \in [1, m], i \neq j)$的倍数，
3. 减去所有$p_{i} * p_{j} * p_{k} (i, j, k \in [1, m], i \neq j \neq k)$的倍数
$\cdots$
剩下的数均与$N$互质，个数为$\phi(N)$
以$m = 3$为例：

$$ \begin{align} N - (\frac{N}{p_{1}} + \frac{N}{p_{2}} + \frac{N}{p_{3}}) + (\frac{N}{p_{1} * p_{2}} + \frac{N}{p_{1} * p_{3}} + \frac{N}{p_{2} * p_{3}}) - (\frac{N}{p_{1} * p_{2} * p_{3}}) \\\\ = N * (1 - \frac{1}{p_{1}}) * (1 - \frac{1}{p_{2}}) * (1 - \frac{1}{p_{3}}) \end{align} $$

int phi(int a) {
    int ret = a;
    for (int i = 2; i <= a / i; i++) {
        if (a % i == 0) {
            while (a % i == 0) a /= i;
            ret = ret / i * (i - 1);
        }
    }
    if (a > 1) ret = ret / a * (a - 1);
    return ret;
}

筛法求欧拉函数（求$1$ ~ $n$中每个数的欧拉函数之和是多少）

借鉴线性筛法的思路
当$i$为质数时，$\phi(i) = i - 1$
枚举质数过程中：
当$p_{j} \mid i$时，$p_{j}$一定是$i$的最小质因子，则

$$ \phi(i) = i * (1 - \frac{1}{p_{1}}) * \cdots * (1 - \frac{1}{p_{j}}) \\\\ \phi(p_{j} * i) = p_{j} * i * (1 - \frac{1}{p_{1}}) * \cdots * (1 - \frac{1}{p_{j}}) = p_{j} * \phi(i), (p_{1} > \cdots > p_{j}) $$
当$p_{j} \nmid i$时，$p_{j}$一定小于$i$的最小质因子，$p_{j}$也一定是$p_{j} * i$的最小质因子

$$ \phi(i) = i * (1 - \frac{1}{p_{1}}) * \cdots * (1 - \frac{1}{p_{k}}) \\\\ \phi(p_{j} * i) = p_{j} * i * (1 - \frac{1}{p_{1}}) * \cdots * (1 - \frac{1}{p_{k}}) * (1 - \frac{1}{p_{j}}) = (p_{j} - 1) * \phi(i), (p_{1} > \cdots > p_{k} > p_{j}) $$

typedef long long LL;

const int N = 1e6 + 10;

int primes[N], cnt;
LL phi[N];
bool st[N];

LL get_phi(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) { primes[cnt++] = i, phi[i] = i - 1; }
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            } else {
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            }
        }
    }
    LL ret = 0;
    for (int i = 1; i <= n; i++) ret += phi[i];
    return ret;
}

欧拉定理

【内容】：若对于正整数$a$和$n$有$(a, n) = 1$，则$a^{\phi(n)} \equiv 1 (mod \; n)$
【证明】：
假设$A = \lbrace a_{1}, a_{2}, \cdots, a_{\phi(n)} \rbrace$是$1$ ~ $n$中$\phi(n)$个互不相同的与n互质的数，且$0 < a_{1} < \cdots < a_{\phi(n)} < n$
构造一组新的数$Z = \lbrace a * a_{1}, \cdots, a * a_{\phi(n)} \rbrace$
【引理1】：$z_{i}$之间两两模$n$不同余（反证法）
假设$\; \exists \; z_{i} \equiv z_{j} (mod \; n), i \neq j$
则$z_{i} - z_{j} \equiv 0 (mod \; n) \implies a * (a_{i} - a_{j}) \equiv 0 (mod \; n) \implies a_{i} - a_{j} \equiv 0 (mod \; n)$，与上述假设矛盾
【引理2】：$(z_{i}, n) = 1, i = 1 \cdots \phi(n)$
则$A$和$Z$在模$n$的情况下是同一组数的不同排列，即
$a_{1} * \cdots * a_{\phi(n)} \equiv z_{1} * \cdots * z_{\phi(n)} (mod \; n) \implies (a^{\phi(n)} - 1) * a_{1} * \cdots * a_{\phi(n)} \equiv 0 (mod \; n) \implies a^{\phi(n)} \equiv 1 (mod \; n)$

费马小定理

【内容】：基于欧拉定理，当$n$为质数时，$a^{\phi(n)} \equiv 1 (mod \; n) \implies a^{n - 1} \equiv 1 (mod \; n)$

（4）快速幂

快速幂

求$a^{k} \; mod \; p \; (1 \leq a, k, p \leq 2 * 10 ^ 9)$
$O(\log{k})$

typedef long long LL;

LL qmi(int a, int k, int p) {
    LL ret = 1;
    while (k) {
        if (k & 1) ret = ret * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return ret;
}

快速幂求逆元

【逆元定义】：若整数$b$，$m$互质，并且对于任意的整数$a$，如果满足$b \mid a$，则存在一个整数$x$，使得$\frac{a}{b} \equiv a * x (mod \; m)$，则称$x$为$b$的模$m$乘法逆元，记为$b^{-1}(mod \; m)$。
$b$存在乘法逆元的充要条件是$b$与模数$m$互质。当模数$m$为质数时，$b^{m - 2}$即为$b$的乘法逆元。

（5）扩展欧几里得算法

【裴蜀定理】：对于任意正整数$a$和$b$，一定存在非零整数$x$和$y$，使得$ax + by = (a, b)$
递推：$(a, b) = (b, a \% b)$
$ax + by = by_{0} + (a - \lfloor \frac{a}{b} \rfloor * b)x_{0} \implies x = x_{0}, y = y_{0} - \lfloor \frac{a}{b} \rfloor * x_{0}$

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

解线性同余方程

方程$a * x \equiv b (mod \; m)$有解的充要条件是$(a, m) \mid b$

（6）中国剩余定理

$m_{1}, m_{2}, \cdots, m_{k}$为$k$个两两互质的正整数，解如下线性同余方程组：
$$ \begin{cases} x \equiv a_{1} \; (mod \; m_{1}) \\\\ x \equiv a_{2} \; (mod \; m_{2}) \\\\ \cdots \\\\ x \equiv a_{k} \; (mod \; m_{k}) \end{cases} $$
【结论】：$x = (a_{1} * M_{1} * M_{1}^{-1} + a_{2} * M_{2} * M_{2}^{-1} + \cdots + a_{k} * M_{k} * M_{k}^{-1}) \; mod \; M$
其中$M = m_1 * m_2 * \cdots * m_k, M_i = \frac{M}{m_i}, M_i^{-1}表示M_i模m_i的逆元$

表达整数的奇怪方式

本题并未给出两两互质的条件，因此无法直接用中国剩余定理的结论得到答案
推导：
$ 每次只考虑将两个方程合并 \begin{cases} x \equiv a_{1} \; (mod \; m_{1}) \\\\ x \equiv a_{2} \; (mod \; m_{2}) \\\\ \end{cases} \\\\ 方程可重写为 x = k_1 * a_1 + m_1 = k_2 * a_2 + m_2, (k_1, k_2 \in Z) \\\\ \implies k_1 * a_1 - k_2 * a_2 = m_2 - m_1 \implies 有解的充要条件为 (a1, a2) \mid (m_2 - m_1) \\\\ 假设方程有解，通过扩展欧几里得算法得到两个特解k_1^0和k_2^0，k \in Z，d = (a_1, a_2) \\\\ 需要将特解扩大\frac{m_2 - m_1}{d}倍使得方程两边相等 \\\\ 则通解可以表示为：\\\\ \begin{cases} k_1 = k_1^0 + k * \frac{a_2}{d} \\\\ k_2 = k_2^0 + k * \frac{a_1}{d} \\\\ \end{cases} \\\\ 则 x = (k_1^0 + k * \frac{a_2}{d}) * a_1 + m_1 = k * (\frac{a_1 * a_2}{d}) + (k_1^0 * a_1 + m_1) \\\\ 于是得到新的同余方程 x \equiv (k_1^0 * a_1 + m_1) \; (mod \; (\frac{a_1 * a_2}{d})) \\\\ 将上述过程重复n - 1次就能将n个同余方程合并为一个方程，于是就能求出解x $

LL exgcd(LL a, LL b, LL &x, LL &y) {}

int main() {
    int n; cin >> n;
    LL a1, m1; cin >> a1 >> m1;
    bool has_answer = true;
    for (int i = 0; i < n - 1; i ++ ) {
        LL a2, m2, k1, k2; cin >> a2 >> m2;
        LL d = exgcd(a1, a2, k1, k2);
        if ((m2 - m1) % d) { has_answer = false; break; }
        k1 *= (m2 - m1) / d;
        int t = abs(a2 / d);
        k1 = (k1 % t + t) % t;
        m1 = k1 * a1 + m1;
        a1 *= t;
    }
    if (has_answer) cout << (m1 % a1 + a1) % a1;
    else puts("-1");
    return 0;
}

2. 高斯消元

$m$个方程，$n$个未知数的线性方程组

$ \begin{cases} a_{11}x_1 &+& a_{12}x_2 &+& \cdots &+& a_{1n}x_n &=& b_1 \\\\ a_{21}x_1 &+& a_{22}x_2 &+& \cdots &+& a_{2n}x_n &=& b_2 \\\\ \vdots & & \vdots & & \vdots & & \vdots & & \vdots \\\\ a_{m1}x_1 &+& a_{m2}x_2 &+& \cdots &+& a_{mn}x_n &=& b_m \\\\ \end{cases} \to \begin{pmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1n} & b_1 \\\\ a_{21} & a_{22} & a_{23} & \cdots & a_{2n} & b_2 \\\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\\\ a_{m1} & a_{m2} & a_{m3} & \cdots & a_{mn} & b_m \\\\ \end{pmatrix} $
【初等行变换】：把某一行乘一个非零的数，交换某两行，把某行的若干倍加到另一行
【解的个数】：根据最后得到的上三角矩阵判断，如果是完美的阶梯型矩阵，则有唯一解；如果存在$0 = b(b \neq 0)$的行，则无解；否则有无穷解（存在$0 = 0$的行）

（1）解线性方程组

【步骤】：
枚举每一列c：
1. 找到当前这一列绝对值最大的一行；
2. 将该行换到未固定的方程的最上方，之后将该方程固定；
3. 将该行第一个非零数变成1；
4. 将下方所有行的第c列消成0

int gauss() {
    int c, r;

    for (c = 0, r = 0; c < n; c++) {
        int t = c;

        for (int i = r; i < n; i++)
            if (abs(a[i][c]) > abs(a[t][c]))
                t = i;

        if (abs(a[t][c]) < eps) continue;

        for (int i = c; i < n + 1; i++) swap(a[t][i], a[r][i]);
        for (int i = n; i >= 0; i--) a[r][i] /= a[r][c];

        for (int i = r + 1; i < n; i++)
            if (abs(a[i][c]) > eps)
                for (int j = n; j >= c; j--)
                    a[i][j] -= a[r][j] * a[i][c];

        r++;
    }

    if (r < n) {
        for (int i = r; i < n; i++)
            if (abs(a[i][n]) > eps)
                return 0;

        return 1;
    }

    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            a[i][n] -= a[j][n] * a[i][j];

    return 2;
}

3. 组合计数

不同范围对复杂度要求不同
$C_a^b = C_{a - 1}^b + C_{a - 1}^{b - 1} = \frac{a!}{b! (a - b)!}$

（1）求$C_a^b \; mod \; (10^9 + 7)$

$O(n^2)$
$1 \leq b \leq a \leq 2000$
根据公式预处理出所有组合数的值

void init() {
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j <= i; j ++ )
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}

（2）求$C_a^b \; mod \; (10^9 + 7)$

$O(n\log{n})$
$1 \leq b \leq a \leq 10^5$
预处理出所有数的阶乘和逆元，mod是质数，可以用费马小定理

void init() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i ++ ) {
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

（3）求$C_a^b \; mod \; p$

$O(p\log{p}\log_{p}{N})$
$1 \leq b \leq a \leq 10^{18}, 1 \leq p \leq 10^5, p是质数$
【Lucas定理】：$C_a^b \equiv C_{a\;mod\;p}^{b\;mod\;p} * C_{a / p}^{b / p} \; (mod\;p)$

LL C(int a, int b) {
    LL ret = 1;
    for (int i = 1, j = a; i <= b; i ++, j -- ) {
        ret = ret * j % p;
        ret = ret * qmi(i, p - 2) % p;
    }
    return ret;
}

LL lucas(LL a, LL b) {
    if (a < p && b < p) return C(a, b);
    return C(a % p, b % p) * lucas(a / p, b / p) % p;
}

（4）求$C_a^b$

$1 \leq b \leq a \leq 5000$
没有求模运算，结果会很大
分子分母分解质因数，再把所有质因数乘起来（大数相乘）

const int N = 5010;

int sum[N], primes[N], cnt;
bool st[N];

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int get_exp(int a, int p) {
    int ret = 0;
    while (a) {
        ret += a / p;
        a /= p;
    }
    return ret;
}

vector<int> mul(vector<int> &a, int b) {
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i++) {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t) {
        c.push_back(t % 10);
        t /= 10;
    }

    return c;
}

int main() {
    int a, b; cin >> a >> b;
    get_primes(a);

    for (int i = 0; i < cnt; i++) {
        int p = primes[i];
        sum[i] = get_exp(a, p) - get_exp(a - b, p) - get_exp(b, p);
    }

    vector<int> ret = {1};
    for (int i = 0; i < cnt; i++)
        for (int j = 0; j < sum[i]; j++)
            ret = mul(ret, primes[i]);

    for (int i = ret.size() - 1; i >= 0; i--) cout << ret[i];

    return 0;
}

（5）卡特兰数

$C_{2n}^n - C_{2n}^{n - 1} = \frac{C_{2n}^n}{n + 1}$

4. 容斥原理

$$ |S_1 \bigcup S_2 \bigcup \cdots \bigcup S_n| = \sum_i{|S_i|} - \sum_{i, j}{|S_i \bigcap S_j|} + \sum_{i, j, k}{|S_i \bigcap S_j \bigcap S_k|} - \cdots $$
每个集合被不重不漏的计算次数：$\sum_{i = 1}^n{C_n^i * (-1)^{i - 1}} = 1$