注意：本篇不包含组合数学，组合数学会另开一篇。（因为组合数学没那么多知识点啦，还是记录一些题目为主。）

质数

1. 不超过 $N$ 的质数个数大约为 $\frac{N}{\ln N}$。
2. 线性筛法，每次用最小的质因子筛质数，可以用来 $O(n)$ 快速筛诸如欧拉函数、因子个数等。
3. $N = p_1 ^ {c_1} * … * p_k^{c_k}$

约数

1. $N$ 的正约数集合：$\{p_1 ^ {b_1} * … * p_k^{b_k}\}$，其中 $0\leq b_i \leq c_i$
2. $N$ 的正约数个数：$\prod_{i = 1}^{k}(c_i + 1)$
3. $N$ 的正约数和：$\prod_{i = 1}^{k}\left (\sum_{j = 0}^{c_i}(p_i) ^ j \right )$
4. $int$ 范围内约数个数最多的数有 $1600$ 个约数

最大公约数

1. $\forall a,b \in N$, 有 $a \geq b, \gcd(a, b) = \gcd(b, a - b) = \gcd(a, a - b)$
2. $\forall a,b \in N$, 有 $\gcd(2a, 2b) = 2 \gcd(a, b)$
3. $\forall a,b \in N, b \ne 0$, 有 $\gcd(a, b) = \gcd(b, a \mod b)$

积性函数

1. 当 $a, b$ 互质时，有 $f(ab) = f(a) \times f(b)$，则称 $f$ 为积性函数
2. 若 $f$ 是积性函数，且 $n = \prod_{i = 1}^{k}p_i ^ {c_i}$，则 $f(n) = \prod_{i = 1}^{k}f(p_i^{c_i})$

互质与欧拉函数

1. $\forall a, b \in N$，若 $gca(a, b) = 1$，则 $a, b$ 互质

2. $\varphi (N) = N * \prod_{p | N}(1 - \frac{1}{p})$，证明参考容斥原理

3. $\forall n > 1$，$1 \sim n$ 中与 $n$ 互质的数的和为 $n \times \varphi(n) \div 2$

4. 若 $a, b$ 互质，则 $\varphi(a, b) = \varphi(a)\varphi(b)$，即 $\varphi$ 为积性函数

5. 设 $p$ 为质数，若 $p | n$ 且 $p^2|n$，则 $\varphi(n) = \varphi(\frac{n}{p}) \times p$

6. 设 $p$ 为质数，若 $p|n$ 且 $p^2\nmid n$，则 $\varphi(n) = \varphi(\frac{n}{p}) \times (p - 1)$

7. $\sum_{d | n}\varphi(d) = n$

证明($7$)：令 $f(n) = \sum_{d|n} \varphi(d)$，设 $n, m$ 互质，则 $f(nm) = \sum_{d | nm} \varphi(d) = \sum_{d | n}\varphi(d) \times \sum_{d | m}\varphi(d) = f(n) \times f(m)$

​ 又 $f(p^k) = \sum_{d | p^k} \varphi(d) = \varphi(1) + \varphi(p) + … + \varphi(p^k) = 1 + p - 1 + p^2 - p + … + p^k - p^{k - 1} = p^k$

​ $\therefore f(n) = \prod_{i = 1}^{k}f(p_i^{c_i}) = \prod_{i = 1}^{k}p_i^{c_i} = n$

同余

1. 对于 $\forall a \in [0, m - 1]$，集合 ${a + km}(k \in Z)$ 的所有数模 $m$ 同余，该集合称为一个模 $m$ 的同余类，记为 $\bar{a}$
2. 模 $m$ 的同余类共有 $m$ 个，分别为 $\bar{0}, \bar{1}, … \bar{m - 1}$，它们构成 $m$ 的完全剩余系。
3. $1 \sim m$ 中与 $m$ 互质的数共有 $\varphi(m)$ 个，它们构成 $m$ 的简化剩余系。
4. 简化剩余系关于模 $m$ 乘法封闭（乘法封闭即 $\forall a, b \in S$，$ab \in S$）。

欧拉定理

1. 若正整数 $a, n$ 互质，则 $a ^ {\varphi(n)} \equiv 1 \pmod{n}$

证明：设 $n$ 的简化剩余系为 $\{\bar{a_1}, \bar{a_2}, …, \bar{a_{\varphi(n)}}\}$，对于 $\forall a_i, a_j$，若 $a\times a_i \equiv a \times a_j \pmod n$，则可推出 $a_i \equiv a_j \pmod n$，矛盾。

​ 所以，当 $a_i \ne a_j$ 时，$\bar{aa_i}$ 与 $\bar{aa_j}$ 代表不同的同余类。

​ 根据上文所述的乘法封闭，$\bar{aa_i}$ 也在简化剩余系中，所以 $\{\bar{aa_1}, \bar{aa_2}, …, \bar{aa_{\varphi(n)}}\}$ 也是 $n$ 的简化剩余系。

​ 注意到 $a^{\varphi(n)}$ 与 $n$ 互质，所以 ：

​ $$a^{\varphi(n)}a_1a_2…a_{\varphi(n)} \equiv (aa_1)(aa_2)…(aa_{\varphi(n)}) \equiv a_1a_2…a_{\varphi(n)} \pmod n$$

​ 因为 $a_1a_2…a_{\varphi(n)}$ 与 $n$ 互质，所以 $a^{\varphi(n)} \equiv 1 \pmod n$

1. 由欧拉定理引申出费马小定理：对于任意正整数 $a, p$ 互质且 $p$ 为质数，则 $a^{p - 1} \equiv 1 \pmod p$

证明：由欧拉定理得 $a^{\varphi(p)} \equiv 1 \pmod p$，又因为 $p$ 为质数，所以 $\varphi(p) = p - 1$，所以 $a^{p - 1} \equiv 1 \pmod p$

1. 费马小定理也可以写成：对于任意整数 $a$，若 $p$ 是质数，有 $a^p \equiv a \pmod p$
2. 欧拉定理的推论：若正整数 $a, n$ 互质，则对于任意正整数 $b$，有 $a^b \equiv a^{b \bmod \varphi(n)} \pmod n$

证明：设 $b = q \times \varphi(n) + r$，其中 $0 \leq r < \varphi(n)$，即 $r = b \bmod \varphi(n)$

​ 那么 $a^b = a^{q \times \varphi(n) + r} = (a^{\varphi(n)})^q \times a^r \equiv 1^q \times a^r \equiv a^r \equiv a^{b \bmod \varphi(n)} \pmod n$

1. 由欧拉定理的推论，对于乘方算式，可以将底数对 $p$ 取模，指数对 $\varphi(p)$ 取模
2. 当 $a, n$ 不一定互质且 $b > \varphi(n)$ 时，有 $a^b \equiv a^{b \bmod \varphi(n) + \varphi(n)} \pmod n$，可以通过寻找 $a^b \pmod n$ 的指数循环节来证明。

拓展欧几里得

1. 裴蜀定理（Bézout 定理）：对于 $\forall a, b \in Z$，存在一对整数 $x, y$，满足 $ax + by = gcd(a, b)$

证明：当 $b = 0$ 时，显然有 $x = 1, y = 0$。

​ 当 $b > 0$ 时，有 $\gcd(a, b) = \gcd(b, a \bmod b)$。存在 $x, y \in Z$ 使得 $b \times x + (a \bmod b) \times y = \gcd(b, a \bmod b)$

​ 变型得，$ay + b(x - \lfloor \frac{a}{b} \rfloor y)$，令 $x^{‘} = y, y^{‘} = x - \lfloor \frac{a}{b} \rfloor y$，可得 $ax^{‘} + by^{‘} = gcd(b, a \bmod b) = gcd(a, b)$

​ 对欧几里得算法的过程采用数学归纳法即可证明裴蜀定理。

1. 设 $d$ 为 $\gcd(a, b)$，根据上述过程可以求出 $ax + by = d$ 的一组特解 $x_0, y_0$

2. 对于方程 $ax + by = c$，它有解的充要条件是 $d | c$，满足该条件则原方程的一组特解为 $\frac{c}{d}x_0, \frac{c}{d}y_0$

3. 由于 $a(x + k\frac{b}{d}) + b(y - k\frac{a}{d}) = ax + by$，所以 $ax + by = c$ 的通解可表示为：

$$x = \frac{c}{d}x_0 + k\frac{b}{d}, y = \frac{c}{d}y_0 - k\frac{a}{d} (k \in Z)$$

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

线性同余方程

长相类似 $a \times x \equiv b \pmod m$，其等价于 $a\times x - b$ 为 $m$ 的 $-y$ 倍，于是可以得到 $ax +ym = b$。

根据拓展欧几里得，该方程有解当且仅当 $\gcd(a, m) | b$，有解时直接拓展欧几里得做即可。

乘法逆元

若整数 $b, m$ 互质，且 $b | a$，则存在整数 $x$ 满足 $a \div b \equiv a \times x\pmod m$，$x$ 即为 $b$ 的模 $m$ 乘法逆元，记为 $b^{-1}\pmod m$

可以用费马小定理证明 $x = b^{m - 2}$，可以用于解决除法取模。

### 中国剩余定理

设 $m_1, m_2, …, m_n$ 是两两互质的整数，$m = \prod_{i = 1}^{n}m_i$，$M_i = m \div m_i$，$t_i$ 为 $M_it_i \equiv 1 \pmod {m_i}$ 的一个解。对于任意 $n$ 个整数 $a_1,a_2,…,a_n$ 组成的方程组：

$$\left\{\begin{matrix} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_n \pmod{m_n} \end{matrix}\right.$$

有整数解 $x = \sum_{i = 1}^{n}a_iM_it_i$

拓展中国剩余定理

当 $m_1, m_2, …, m_n$ 不两两互质时，便无法使用中国剩余定理，好在我们可以借助数学归纳法求解。

设已经求出前 $k - 1$ 个方程的一个解 $x$，记 $m = \operatorname{lcm}(m_1, m_2, \cdots, m_{k - 1})$，则前 $k - 1$ 个方程的通解为 $x + im(i \in Z)$。

那么对于第 $k$ 个方程，我们求出整数 $t$ 使得 $x + tm \equiv a_k \pmod{m_k}$，变形得 $tm \equiv a_k - x \pmod{m_k}$，可以使用拓展欧几里得求解。

求解出 $t$ 后，则 $x^{‘} = x + tm$ 为前 $k$ 个方程的通解，一直做到第 $n$ 个方程即可。

// 洛谷模板题暴 LL，遂 int128

__int128_t n, a, m, M, x;

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

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

__int128_t qmul(__int128_t a, __int128_t b, __int128_t p) {
    __int128_t res = 0;
    while (b) {
        if (b & 1) res = (res + a) % p;
        b >>= 1;
        a = (a + a) % p;
    }
    return res;
}

int main() {
    n = read();
    rep(i, 1, n) {
        m = read(), a = read();
        if (i == 1) {
            x = a, M = m;
            continue;
        }
        __int128_t k1, k2; exgcd(M, m, k1, k2);
        __int128_t d = exgcd(M, m, k1, k2), c = (a - x % m + m) % m;
        if (c % d != 0) {
            puts("-1");
            return 0;
        }
        __int128_t t = k1 * c / d % m;
        x = x + t * M; M = M * m / d; x = (x % M + M) % M;
    }
    x = (x % M + M) % M;
    write(x);
    return 0;
}

高次同余方程

喵？

矩阵乘法

1. 对于 $n \times m$ 矩阵 $A, B$ 则 $C = A \pm B \Leftrightarrow \forall i \in[1, n], j\in[1,m],C_{i, j} = A_{i, j} \pm B_{i, j}$，即对应位置相加减
2. 对于 $n \times m$ 矩阵 $A$ 和 $m \times p$ 矩阵 $B$，$C = A \times B$ 是 $n \times p$ 矩阵，其中 $\forall i \in[1, n], j\in[1, p]$，有 $C_{i, j} = \sum_{k = 1}^{m} A_{i, k} \times B_{k, j}$
3. 矩阵乘法满足结合律，分配律，但不满足交换律
4. 矩阵乘法加速递推问题的特点：
5. 可以抽象出一个长度为 $n$ 的向量，该向量在每个单位时间发生一次变化
6. 变化的形式为线性递推
7. 该递推式在每个时间本身保持不变
8. 向量变化时间很长，但向量长度 $n$ 不大
9. 对于矩阵乘法加速递推问题，若状态矩阵中的第 $x$ 个数对下个状态的 $y$ 产生影响，则把转移矩阵的 $(x, y)$ 赋值为适当的系数
10. 矩阵乘法加速递推的时间复杂度是 $O(n ^ 3logT)$

线性空间

线性空间是一个关于向量加法与标量乘法（$k \times a$，其中 $a$ 为向量，$k$ 为标量）。

若向量 $b$ 能够被向量 $a_1, a_2, …, a_k$ 通过上述操作得到，那么称向量 $b$ 能被向量 $a_1, a_2, …, a_k$ 表出。

向量 $a_1, a_2, …, a_k$ 能表出的所有向量组成一个线性空间，$a_1, a_2, …, a_k$ 被称为该线性空间的生成子集。

任意选出线性空间中的若干个向量，若不存在向量能被其它向量表出，则称这些向量线性无关，否则称为线性相关。

线性空间的极大线性无关生成子集被称为线性空间的基。显然一个线性空间的所有基包含的向量个数都相等，定义为线性空间的维数。

一个例子是空间直角坐标系中的一个基就是 $\{(1, 0, 0), (0, 1, 0), (0, 0, 1)\}$，维数是 $3$。

对于一个 $n \times m$ 的矩阵，将它的每一行看作长度为 $m$ 的行向量，那么这 $n$ 个行向量能够表示出的所有向量构成一个线性空间。这个线性空间的维度称为“行秩”，同样地可以定义“列秩”。显然“行秩”等于“列秩”，合称为秩。

将 $n \times m$ 矩阵进行高斯消元得到的简化阶梯形矩阵的所有非零行向量线性无关，且不改变原有的线性空间。所有的非零行向量即为该线性空间的基，非零行向量的个数即为矩阵的秩。

异或线性空间

定义表出为整数 $b$ 能由整数 $a_1, a_2, \cdots, a_k$ 经过异或得到。异或空间为 $a_1, a_2, \cdots, a_k$ 能标出的所有整数，$a_1, a_2, \cdots, a_k$ 即为异或空间的生成子集。

任意选出异或空间的若干个整数，如果存在一个数能被其它数表出，责成这些整数线性相关，否则线性无关。

异或空间的基就可以定义为异或空间中的一个极大线性无关子集。

将异或空间中的所有数写作 $m$ 位二进制数，通过高斯消元，所有非 $0$ 的整数构成异或空间的基。

设一个对于 $a_1, a_2, \cdots, a_n$，从中找出 $t$ 个线性无关的整数，作为基，所以异或空间包含 $2^t$ 个互不相等的整数，这样的到的是一个“去重异或集合”。我们如何得到不去重的呢？

从剩下的 $n - t$ 个数中选出若干个显然有 $2^{n - t}$ 种方法。设选取的整数异或起来为 $x$，把基底能表示出的 $2^t$ 个数分别与 $x$ 异或就能得到 $2^t$ 个互不相等的整数（而这些数一定是基底能表示的 $2^t$ 个数）。所以，每种取法与基底相结合恰好遍历“去重异或集合”一次。

总结一下，对于一个“去重异或集合”将它包含的 $2^t$ 个整数各重复 $2^{n - t}$ 次可以形成“不去重异或集合”。