0x1f Bézout 定理
如果 \(a,b\) 均为整数，则方程 \(ax + by = \gcd(a,b)\) 一定有解。
可以使用构造法证明，也就是 \(exgcd\)。。。
证明：
对于 \(ax + by = c\)，对其进行变换 \(bx + (a \% b)y = c\)。
如果我们知道后者的解 \(x_1,y_1\)，那么有
待定系数法得出 \(\begin{cases} x_0 = y1 \\ y_0 = x_1 - \lfloor \cfrac{a}{b} \rfloor \times y1 \end{cases}\)
显然根据辗转相除法，一定有 \(a\%b = 0\) 时，此时 \(ax = c\)，\(x = \dfrac{c}{a}\)。
而当 \(a\%b = 0\) 时，\(a\) 为 \(\gcd(a,b)\)，即 \(x = \dfrac{c}{\gcd(a,b)}\)。
当 \(c | \gcd(a,b)\) 时， \(x\) 有整数解。
证毕。\(\square\)
0x2f exgcd
想必你也已经发现了，根据证明 Bézout 定理 的过程，我们已经可以知道 \(ax + by = \gcd(a,b)\) 的一个解了。
那么这一节主要讲各种解的算法。
-
判断 \(ax + by =c\) 有无解
\(\textbf{Theorem}\)：一个 \(ax + by =c\) 方程有解，当且仅当 \(c | \gcd(a,b)\)。
必要性：前文已经阐述。
充分性：\(\gcd(a,b)|a \and \gcd(a,b)|b \to \gcd(a,b)|c\)。
-
通解
先举个例子：
\(3x + 2y = 18\)
你会怎么解？
首先随便找到一组解 \(x = 4,y = 3\)。
再减小 \(x\)，增加 \(y\) 就找到另一组解 \(x = 2,y = 6\)。
那么设 \(x\) 的变化量 \(\Delta x\)，\(y\) 的变化量 \(\Delta y\)。
显然 \(a(x + \Delta x) + b(y + \Delta y) = c\)。
有 \(a \Delta x + b \Delta y = 0\)。
显然我们想让 \(\Delta x/\Delta y\) 绝对值最小。
\(\Delta x\) 取 \(\cfrac{a}{\gcd(a,b)}\) 时。
原式转换成 \(1 - 1 = 0\)。
所以我们得到了通解。
\[a(x + k\cfrac{a}{\gcd(a,b)}) + b(y - k\cfrac{b}{\gcd(a,b)}) = c \] -
\(x/y\) 最小正整数解
对于 \(x = x + k\cfrac{a}{\gcd(a,b)}\) 最小正整数解，设 \(g = \cfrac{a}{\gcd(a,b)}\)
在 \((x \%g + g)\%g\) 产生（因为 \(g\) 是步长）。
-
方程是否有正整数解
我们一定有 \(x_{\min} \to y_{\max}\)，对吧！
此时若 \(y_{\max} \le 0\)，则无正整数解。
-
推推推论
\(\sum_{i=1}^n {a_i \times x_i} = c\) 的通解，当且仅当 \(c | \gcd_{i=1}^n a_i\)
0x3f 乘法逆元
定义：\(a \times a^{-1} \equiv 1 \pmod{p}\) ，\(a^{-1}\) 为 \(a\) 在模 \(p\) 意义下的逆元。
应用场景：在模意义下除以一个数时，只能乘它的逆元。
下面给出三种求逆的方法，在不同地方用到：
-
费马小定理
优点：大部分人都会，求单个逆元
缺点：要求互素。
设 \(n\) 是素数，\(a\) 与 \(n\) 互素，有 \(a^{n-1} \equiv 1 \pmod n\)。
变形 \(a \times a^{n-2} \equiv 1 \pmod n\)。
所以此时 \(a^{n-2}\) 为逆元。
-
\(\textbf {exgcd}\) 求解
\(ax \equiv 1 \pmod n\)，求 \(x\)。
即 \(ax + bn = 1\)。
\(exgcd\) 求解即可。
-
递推求逆元
我们知道 \(1^{-1} = 1 \pmod n\)。
首先有 \(i \times \lfloor \dfrac{p}{i} \rfloor + p\mod i \equiv 0 \pmod p\)。
\(p \mod i\) 的逆元我们已经一定求出来了，整个式子同乘 \(i^{-1} (p \pmod i)^{-1}\)。
\[i^{-1} = -(p \pmod i)^{-1} \times \lfloor \dfrac{p}{i} \rfloor \]递推式证毕。\(\square\)
-
补充：倒推求逆元法
为什么要在这里介绍呢？因为它可以在 \(O(n)\) 内递推任意 \(n\) 个数的逆元。
证明：
假设我们有一列数 \(a_1,a_2,a_3,\dots,a_n\)。
- 用循环求出数列的前缀积。
- 用 \(exgcd\) 或费马小定理计算 \(\prod_{i=1}^n a_i\) 的逆元。
- 根据 \(\dfrac{1}{\prod_{i=1}^{k-1} a_i} = \dfrac{a_k}{\prod_{i=1}^{k} a_i}\)，求出任意前缀积的逆元。
- 根据 \(\dfrac{1}{a_k} = \dfrac{\prod_{i=1}^{k-1} a_i}{\prod_{i=1}^{k} a_i}\)，求出任意 \(a_i\) 的逆元。
证毕。\(\square\)
0x4f 中国剩余定理
对于下列的同余方程组，能否知道解的情况呢？
其中 \(m_i\) 两两互质。
中国剩余定理给出了解答，我们会阐述其充要性。
构造：
-
设 \(M = \prod_{i=1}^n m_i\)。
-
设 \(M_i = \dfrac{M}{m_i}\)。
-
设 \(t_i = M^{-1} \pmod m_i\)
-
\[x = kM + \sum_{j=1}^n {a_i t_i M_i} \]
证明：
-
充分性：
由于 \(t_i\) 是 \(M_i\) 的逆元，有 \(a_i t_i M_i \equiv a_i \pmod{m_i}\)。
由于 \(M\) 的定义，\(a_i t_i M_i \equiv 0 \pmod{m_j} (i \ne j)\)。
\(x = kM + \sum_{j=1}^n {a_i t_i M_i} \equiv 0 + (a_i + \sum_{j=1,j \ne i}^n 0) \pmod{m_i}\)。
综上得证。\(\square\)
-
必要性
假设存在另一个解，\(x_1 \equiv x \pmod{M}\) 不成立（这里模 \(M\) 是消除步长），但是由于 \(x_1 \equiv a_i \equiv x \pmod{m_i}\)。
推广得到 \(\forall i,x_1 \equiv x \pmod{m_i}\)。
我们可以得到 \(x_1 \equiv x \pmod{M}\)。
假设推翻，固有唯一通解。
证毕。\(\square\)