你猜为什么我数学那么差？
1. 从欧几里得算法到扩展欧几里得算法
我们一般用欧几里得算法求最大公约数，它差不多就这样
，但是实际上这里的 \(3\) 是一个除以 \(5\) 余 \(3\) 的数，\(7\) 同理，这个时候就能整除了。
其实，我们只需要求出一个 \(\dfrac{1}{b} \equiv x\pmod m\) 的 \(x\)，那么 \(\dfrac{a}{b}\) 就是两边同乘 \(a\) 的结果，这个 \(x\) 就叫做 \(b\) 在模 \(m\) 意义下的逆元，记作 \(b^{-1}\)。\(a / b\) 就是 \(a\times b^{-1}\)。
它怎么求？
- exgcd
转化一下 \(xb\equiv 1 \pmod m\)，线性同余方程组，那 exgcd 随便跑。有解情况是 \(b, m\) 互质。这是一个线性同余方程，具体解法下面会提及。 - 费马小定理
只适用于 \(m\) 为质数，由于 \(a^{p - 1}\equiv 1\pmod m\)，所以 \(a\times a^{p - 2}\equiv 1 \pmod m\)。所以 \(a^{-1} = a^{p - 2}\)。 - 线性递推。
这个就很高级，虽然我觉得它似乎没什么用，因为 OI 里面我们都知道 \(O(n)\) \(O(n\log_2 n)\) 众生平等（划掉
但是学一手以防万一对吧（）
众所周知，\(1^{-1} = 1\)。我们记 \(ki+r = m\)，那么就有
\(ki+r \equiv 0 \pmod m\)。两边同乘 \(i^{-1}\) 得到
\(k + ri^{-1}\equiv 0 \pmod m\) 即 \(i^{-1}\equiv -kr^{-1}\pmod m\)，即 $ i^{-1}\equiv -\lfloor\dfrac{p}{i}\rfloor (p\bmod i)^{-1}\pmod m$
有了逆元我们就可以做模意义下的除法辣✿✿ヽ(°▽°)ノ✿
7. 线性同余方程
\(ax\equiv b\pmod m\)，形如这样的关于 \(x\) 的方程。
脑子告诉我们它等价于这样一个式子 \(ax - km = b\)，拿 exgcd 一跑就行了.
8. 线性同余方程组，模数互质（CRT）
这就是我们幼儿园学习过的韩信点兵问题，但是当时没有学一个一般化（雾）的解法。
它是用来解形如 \(\begin{cases}x \equiv r_1 \pmod {m_1} \\ x \equiv r_2\pmod {m_2} \\ \dots \\ x \equiv r_n \pmod {m_n}\end{cases}\)。其中 \(m_1\sim m_n\) 两两互质。
我们记 \(M = \prod\limits_{i = 1}^n m_1，v_i = (\dfrac{M}{m_i})^{-1}(模 m_i 意义下的)\)，通解形式是 \(ans = \sum\limits_{i = 1}^n \dfrac{M}{m_i}v_ir_i + kM\)，最小解是 \(ans = \sum\limits_{i = 1}^n \dfrac{M}{m_i}v_ir_i \bmod M\)。
证明如下：先指针对一个同余方程 \(x\equiv r_i \pmod {m_i}\) 看，计算它的贡献，为了消去 \(x\) 对其它方程组的影响，我们先给它乘上一个 \(\dfrac{M}{m_i}\)。由于我们答案是求和的，这样做它对其它方程组取余的结果就为 \(0\)，不会影响答案。
我们令 \(x'\dfrac{M}{m_i}\equiv r_i \pmod {m_i}\)，移项得到 \(x' \equiv \dfrac{r_im_i}{M}\pmod {m_i}\)，也就是 \(x' \equiv r_i\times (\dfrac{M}{m_i})^{-1}\pmod {m_i}\)，这里对答案的贡献就是 \(\dfrac{M}{m_i}v_ir_i\)。
CRT 这样的“乘一个倍数消去贡献”的方法很好用，很多题都能用的上，同时对于许多模数有严格限制（比如 NTT）这样的算法，我们可以先拿两个大质数算出解，构造两个同余方程组，然后对于新模数再计算，这样常数固然会比较大，但是相对于 MTT（显而易见我没学过它）好理解十倍甚至九倍（划掉
逆元拿 exgcd 算，代码都是老早之前写的，明天重写一份贴上来 qwq