EXGCD 和 EXCRT
前言
我与这两个算法有很深的渊源。
第一次遇到是三年前的五校联考，\(\text{t1}\) 需要用到，于是我成了全场唯一一个没切 \(\text{t1}\) 的。
第二次是两年前湖南省集，我依稀记得这是第二场的 \(\text{Day1 T2}\)，我花了 \(\text{2.5h}\) 去推 \(\text{exCRT}\) 的式子，加上那题要用 \(\text{SA/SAM}\) 之类的字符串技巧，写出来差不多有 \(\text{7k}\)，尽管我拼尽全力，但最终还是挂成了 \(28\)。导致即使切了 \(\text{Day2 T1}\) 的神秘构造，还是没有翻盘。
第三次是一年前的正睿，这题推的比较快，只写了 \(\text{1h}\) 就过了大样例。但因为没总结过 \(\text{exCRT}\) 的板子，于是喜提没开 \(\text{int128}\)。\(100 \rightarrow 50\)。
三年过去，我终于学会了 \(\text{exCRT}\)。我成功了，我不再是从前的那个自我了。
以下均是我自己推的，所以仅供参考。
正文
假设我们要求不定方程 \(ax + by = c\) 的一组整数解（为方便起见默认 \(a, b, c > 0\)，其余情况也是类似的）。
显然并不是所有这样的方程都有整数解。比如 \(2x + 4y = 1\) 显然无整数解。
我们试着给出一个方程有整数解的充要条件：\(\gcd(a, b) \mid c\)。下面令 \(g = \gcd(a, b), l = \text{lcm}(a, b)\)。必要性较为显然，因为 \(x, y\) 均为整数，且 \(g \mid a, g \mid b\)，所以 \(g \mid ax + by = c\)。
充分性我们后面用 \(\text{exGCD}\) 构造即可。现在考虑我们只需求一组 \(ax + by = g\) 的整数解，求完后只需 \(x \gets x \times \frac{c}{g}, y \gets y \times \frac{c}{g}\) 即可得到原方程的解。
对于求解 \(ax + by = g\) 的问题，我们考虑递归下去求解 \(by + (a \bmod b) = g\)，由于 \(\gcd\) 的性质：\(\gcd(a, b) = \gcd(b, a \bmod b)\)，所以产生出的子问题和原来形式一样。
这样递归下去显然有边界情况，也就是递归求 \(\gcd\) 的边界：\(b = 0\)。此时方程退化为 \(ax + 0y = g\)，因为 \(\gcd\) 运算有 \(\gcd(a, 0) = a\) 的规定，所以 \(a = g\)，方程其实是 \(ax + 0y = a\)。我们令 \(x = 1, y = 0\) 即可。
于是考虑如何通过子问题导出原问题的解。假设在子问题种我们得到一组解 \(x_0, y_0\)，代入得 \(by_0 + (a \bmod b)x_0 = g \Leftrightarrow by_0 + ax_0 - \lfloor \frac{a}{b} \rfloor bx_0 = g \Leftrightarrow b(y_0 - \lfloor \frac{a}{b} \rfloor x_0) + ax_0 = g\)。则可以自然的想到令 \(y = y_0 - \lfloor \frac{a}{b} \rfloor x_0, x = x_0\) 即可。
于是我们成功的求出 \(ax + by = c\) 的一组整数解。一个性质是若 \(b \neq 0\)，这样求出的解满足 \(|x| \le |b|, |y| \le |a|\)（这里允许了参数 \(a, b\) 为负数）。证明可以简单归纳，这里就不展开了。
显然 \(ax + by = c\) 有无数组整数解，在得到一组解后，我们可以通过形如 \(x \gets x + \delta b, y \gets y - \delta a\) 的调整得到所有整数解。
代码实现如下：
void Exgcd (int a, int b, int &x, int &y) {
if (!b) return x = 1, y = 0, void();
Exgcd(b, a % b, y, x);
y -= (a / b) * x;
}
\(\text{exGCD}\) 在 \(\text{OI}\) 中有一个经典应用是求逆元。假设要求 \(a\) 在 \(\bmod p\) 意义下的逆元 \(b\)，即求一个 \(b\) 满足 \(ab \equiv 1 \pmod p\)。由逆元的性质可知只有 \(a \perp p\) 时 \(a\) 才有逆元。
做法是设 \(ab = kp + 1\)，移项成 \(\text{exGCD}\) 的形式就是 \(ab - kp = 1\)，解出一组 \(b, k\) 即可。容易发现保证存在逆元的限制 \(a \perp b\) 恰好对应的 \(\text{exGCD}\) 的要求：\(\gcd(a, p) \mid 1\)，即 \(\gcd(a, p) = 1 \Leftrightarrow a \perp p\)。
接下来进入 \(\text{exCRT}\) 的部分。大家应该听过韩信点兵的故事，形式化的说就是求
\[\begin{cases} x \equiv b_1 \pmod{a_1} \\ x \equiv b_2 \pmod{a_2} \\ \dots\\ x \equiv b_n \pmod{a_n} \end{cases} \]的一个整数解 \(x\)。
首先显然限制可以两两合并，如果我们能够合并两个方程，那么最后一路合并下来就好了。
于是我们考虑如何通过两个限制 \(x \equiv a \pmod b\) 和 \(x \equiv c \pmod d\) 合并成一个新的限制。
将限制分别写成 \(x = k_1a + b\)，\(x = k_2c + d\)，其中 \(k_1, k_2\) 均为整数的形式。合并一下就是 \(k_1a + b = k_2c + d\)。
移一下项容易得到 \(k_1a + k_2(-c) = d - b\)，于是可以令 \(g = \gcd(a, c), l = \text{lcm}(a, c)\)，有解当且仅当 \(g \mid d - b\)。
此时可以 \(\text{exGCD}\) 求出 \(k_1a + k_2(-c) = g\) 的一组解 \(k_1, k_2\) 于是可以得到 \(x \equiv k_1a\frac{d - b}{g} + b \pmod l\)，这里之所以是 \(\bmod l\) 可以参考前面讲的通过调整得出所有整数解的方法。
模板大概是这样的：
LL Exgcd (LL a, LL b, LL &x, LL &y) {
if (!b) return x = (a > 0 ? 1 : -1), y = 0, abs(a);
LL ret = Exgcd(b, a % b, y, x);
return y -= (a / b) * x, ret;
}
void Excrt (LL &a, LL &b, LL c, LL d) {
LL x, y, g = Exgcd(a, -c, x, y), l = a / g * c;
LL r = ((i128(a) * x * ((d - b) / g) + b) % l + l) % l;
a = l, b = r;
}