数学是真的需要写点什么来总结一下，不然隔天就忘（

正睿的课不知道比你谷网校高到哪里去了

贴的课件都是直接用 Mathpix Snipping Tool 识别的，有问题的话不怪我（（

upd：哦草这玩意一个月只能识别 50次然而我在 8.4 就已经用完次数了

一些基础的备忘：$a \mid b$ 表示 $a$ 是 $b$ 的因数。

基础数论

戴言鸽鸽讲得好快……自闭了

裴蜀定理

贴课件

对于任意整数 $a, b, m,$ 则存在整数 $x, y$ 满足 $a x+b y=m,$ 当且仅当 $\operatorname{gcd}(a, b) \mid m$。

若 $a, b$ 之一为 0，结论显然成立。 若否，考虑 $A=\left\{x a+y b \mid(x, y) \in \mathbb{Z}^{2}\right\}$ 中的最小正元素 $d_{0}=x_{0} a+y_{0} b$（这一定存在）。考虑任意 $p=x_{1} a+y_{1} b \in A,$ 设 $p=q d_{0}+r,$ 其中 $0 \leq r<d_{0},$ 则 $r=p-q d_{0} \in A,$ 故 $r=0_{\circ}$ 故 $d_{0} \mid p,$ 则 $d_{0} \mid a, b$。
然后，考虑任意 $d \mid a, b,$ 若 $a=k d$ 而 $b=l d,$ 则 $d_{0}=x_{0} a+y_{0} b=\left(x_{0} k+y_{0} l\right) d,$ 故 $d \mid d_{0},$ 故 $d_{0}=\operatorname{gcd}(a, b)_{\circ}$ 在方程中，若 $m=m_{0} d_{0},$ 则显然有无穷多组解。相反，若有解，则 $|m| \in A$，故 $d_{0}\mid |m|$，即 $d_{0} \mid m$

你发现你什么都看不懂

我们来梳理一下：
给定的是 $a,b,m$，大体证明思路是去某集合 $A$ 中的一元素 $d_0$，证 $d_0=\gcd(a,b)$，之后……写不下去了（（

我们来一条一条的看

若 $a, b$ 之一为 0，结论显然成立。

不妨假设 $b=0$，则 $\gcd(a,b)=a$，原方程化为 $ax=m$。显然当 $a \mid m$ 即 $\gcd(a,b) \mid m$ 时有解。$a=0$ 时同理。

若否，考虑 $A=\left\{x a+y b \mid(x, y) \in \mathbb{Z}^{2}\right\}$ 中的最小正元素 $d_{0}=x_{0} a+y_{0} b$（这一定存在）。

看不懂 $A$ 的定义的话建议百度一下（

考虑任意 $p=x_{1} a+y_{1} b \in A,$ 设 $p=q d_{0}+r,$ 其中 $0 \leq r<d_{0}$

信息量有点大（（

$p$ 事实上是集合 $A$ 中的任何一个元素。

“设 $p=q d_{0}+r,$ 其中 $0 \leq r<d_{0}$” 这句的意思是说设 $q=\left\lfloor\frac{p}{d_{0}}\right\rfloor$，$r=p \bmod d_0$。

则 $r=p-q d_{0} \in A$，故 $r=0$，故 $d_{0} \mid p$，则 $d_{0} \mid a, b$。

我们展开等式右边的 $p$ 和 $d_0$，得到

$\begin{aligned} r &=p-q d_{0} \\ &=x_{1} a+y_{1} b-q\left(x_{0} a+y_{0} b\right) \\ &=a\left(x_{1}-q x_{0}\right)+b\left(y_{1}-q y_{0}\right) \end{aligned}$

不难发现 $r \in A$

由于 $d_0$ 是 $A$ 中最小的正元素，$0 \le r < d_0$（上面的结论），我们得到 $r=0$。

$r=0$ 说明 $p \bmod d_0 = 0$，即 $d_0 \mid p$。

注意到我们的 $p$ 是在 $A$ 中任取的，而 $a,b \in A$，于是我们得到 $d_0 \mid a,b$。

（在 $ax+by$ 中，我们取 $x=1,y=0$ 即得到 $a$，$b$ 同理）

然后，考虑任意 $d \mid a, b,$ 若 $a=k d$ 而 $b=l d$，则 $d_{0}=x_{0} a+y_{0} b=\left(x_{0} k+y_{0} l\right) d$，故 $d \mid d_{0},$ 故 $d_{0}=\operatorname{gcd}(a, b)_{\circ}$

任意 $d\mid a,b$ 都是 $d_0$ 的因数，说明 $d_0=\gcd(a,b)$。

在方程中，若 $m=m_{0} d_{0},$ 则显然有无穷多组解。相反，若有解，则 $|m| \in A$，故 $d_{0}\mid |m|$，即 $d_{0} \mid m$

若方程有解则有 $m=ax+by$，即 $|m| \in A$。由于对于任何 $p\in A$ 有 $d_0 \mid p$，于是我们得出 $d_0 \mid m$，即 $\gcd(a,b) \mid m$。

扩展欧几里得算法

扩展欧几里得算法用于求解形如 $ax+by=\gcd(a,b)$ 的方程（其中 $x,y$ 为未知数）

没有课件（

不妨先把等式两边同除 $\gcd(a,b)$，得到

$\frac{a}{\gcd(a, b)} x+\frac{b}{\gcd(a,b)} y=1$

于是我们可以把求解目标化为解 $ax+by=1$，其中 $a,b$ 互质。

不妨假设 $a>b$

设 $a=qb+r$，其中 $0 \le r < b$

展开式子，得到

$\begin{array}{l} (q b+r) x+b y=1 \\ (q x+y) b+r x=1 \end{array}$

我们发现它又形成了一个新的形如 $ax_0+by_0=1$ 的方程：$bx_0+ry_0=1$，其中 $x_0=qx+y$，$y_0=x$

同时我们发现，如果我们得到了方程 $bx_0+ry_0=1$ 的一组解，我们同样可以得到 $ax+by=1$ 的一组解。

$x=y_0\\ y=x_0-qy_0$

注意到当 $b=0$ 时，$\left\{\begin{array}{l} x=1 \\ y=0 \end{array}\right.$ 是方程的一组特解，于是我们递归求解即得到答案。

乘法逆元

大家都会（

线性同余方程组

太棒了，我正逐渐理解一切

课件

当求解形如 $x\equiv a_i \pmod {m_i}$ 的线性同余方程组时，我们需要使用中国剩余定理（CRT）。

令 $m=\prod_{i=1}^{k} m_{i}$，则在 $m_{i}$ 两两互质时， $x \equiv \sum\limits_{i=1}^{k} M_{i} N_{i} a_{i}\pmod m$，其中$M_{i}=\frac{m}{m_{i}}$，而 $M_{i} N_{i} \equiv 1 \pmod {m_{i}}$（即 $N_i$ 是 $M_i \bmod m_i$ 意义下的逆元）

注意：我们在尝试证明这个结论，即将它带入每个方程验证，而不是推导它。

我们设当前正在尝试带入验证第 $j$ 个方程。

注意到 $x \equiv \sum\limits_{i=1}^{k} M_{i} N_{i} a_{i}\pmod m$ 是一个和式，所以我们可以把它分项讨论。设当前在第 $i$ 项。

当 $i=j$ 时，有 $M_i N_i \equiv 1 \pmod{m_i}$，即 $x=a_i=a_j$。

当 $i\ne j$ 时，$M_{i}=\frac{m}{m_{i}}$ 一定是 $a_j$ 的倍数，即 $x=0$。

综上，我们得到对于每一个方程 $j$，$x \equiv \sum\limits_{i=1}^{k} M_{i} N_{i} a_{i}\pmod m$ 都是它的一个解。

我们来讨论一点其他的东西吧

CRT 事实上是非常有用的东西，所以我打算稍微记一点关于 CRT 的使用的东西

当你需要求解一个式子在 $\bmod p$ 意义下的值，你需要用到模数为质数的一些性质然而 $p$ 是合数，这种时候我们需要使用 CRT 合并答案。

我们移古代猪文一题为例：在算法的某一步我们需要求解 $\sum\limits_{k \mid n} \binom n k \pmod {999911658}$，其中 $999911658$ 是一个合数，等于 $2 \times 3 \times 4679 \times 35617$。

我们可以考虑分别求出 $\sum\limits_{k \mid n} \binom n k$ 在模 $2,3,4679,35617$ 意义下的答案（使用 Lucas 定理），于是我们得到如下线性同余方程组

$\begin{cases} x \equiv a_1 \pmod 2\\ x \equiv a_2 \pmod 3\\ x \equiv a_3 \pmod {4679}\\ x \equiv a_4 \pmod {35617} \end{cases}$

可以使用 CRT 求解该方程组以合并答案。

Q：CRT 没有保证所得解是唯一的，那怎么确保这样合并后的正确性呢？

A：容易证明，任意一个满足 $m_i$ 两两互质的线性同余方程组 $x\equiv a_i \pmod {m_i}$ 都有无穷多个解，只需要把其中一个解加上 / 减去 $\prod m_i$ 即可得到另一个解。

注意到我们的答案需要 $\bmod 999911658$，而该方程组的解在 $\bmod 999911658$ 意义下是唯一的，所以可以放心地使用 CRT 合并答案。

（以上是自己瞎扯的）

欧拉定理 / 扩展欧拉定理

$a^{\varphi(p)} \equiv 1 \pmod p$

$a^x\equiv \begin{cases} a^{x\bmod\varphi(m)} & (a,m)=1 \\ a^{x\bmod\varphi(m)+\varphi(m)} & (a,m)\neq1,x\ge\varphi(m) \end{cases} \pmod m$

这个大家也都会

证明也简单

Lucas 定理

$\binom{n}{m}\bmod p = \binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p\right\rfloor}\cdot\binom{n\bmod p}{m\bmod p}\bmod p$

大家都会

证我也不会证（

不那么基础的数论

大概是扩展 Lucas 定理 / Miller-Rabin 算法 / Pollard's Rho 算法 / 威尔逊定理 / 类欧几里得算法 / BSGS / 二次剩余

之后填坑吧（