Exgcd 和 Excrt 的一些推导
Exgcd
Exgcd 是用来求解二元一次不定方程的算法，即
\[ax+by=c \]根据贝祖定理，该方程有解当且仅当 \(\gcd(a,b) \mid c\)，所以只用求解
\[ax+by=\gcd(a,b) \]又因为
\[\gcd(a,b)=\gcd(b,a \bmod b) \]可以先求解
\[bx'+(a\bmod b)y'=\gcd(a,b) \]变形得
\[bx'+(a-b \lfloor \frac{a}{b}\rfloor)y' = \gcd(a,b) \]\[ay'+b(x'-\lfloor\frac{a}{b}\rfloor y')=\gcd(a,b) \]对比方程 \(ax+by=\gcd(a,b)\)，得
\[\left \{ \begin{matrix} x=y'\\ y=x'-\lfloor\frac{a}{b}\rfloor y' \end{matrix} \right. \]在递归求 \(\gcd(a,b)\) 时顺便求出 \(x,y\) 即可。
对于方程 \(ax+by=c\) 的一组特解 \(x_0,y_0\)，其通解可表示为
\[\left \{ \begin{matrix} x=x_0+kb\\ y=y_0-ka \end{matrix} \right. \text{ }\text{ } (k\in\mathbb{Z}) \]而 Exgcd 求出的是 \(ax+by=\gcd(a,b)\) 的一组特解 \(x_0,y_0\)。
记 \(d=\gcd(a,b)\)，方程 \(ax+by=c\) 的通解可表示为
\[\left \{ \begin{matrix} x=\frac{c}{d}x_0+\frac{b}{d}k \\ y = \frac{c}{d}y_0-\frac{a}{d}k \end{matrix} \right. \text{ } \text{ } (k \in \mathbb{Z}) \]也可表示为
\[\left \{ \begin{matrix} x \equiv \frac{c}{d}x_0 \pmod{\frac{b}{d}}\\ y \equiv \frac{c}{d}y_0 \pmod{\frac{a}{d}} \end{matrix} \right. \]这样我们可以求出 \(x,y\) 的最小正整数值。
Exgcd 还可以用来求解线性同余方程，即
\[ax \equiv b \pmod{m} \]可转化为二元一次不定方程
\[ax+my=b \]使用 Exgcd 求解即可。
Excrt
Excrt 是用来求解线性同余方程组的算法，即
\[\left \{ \begin{matrix} x \equiv a_1 \pmod{m_1}\\ x \equiv a_2 \pmod{m_2}\\ \dots \dots \dots \\ x \equiv a_n \pmod{m_n} \end{matrix} \right. \]考虑已经求解出前 \(k-1\) 个方程组，如何与第 \(k\) 个方程合并。
记 \(x_0\) 为前 \(k-1\) 个方程组的解，\(M=\text{lcm}_{i=1}^{k-1} m_i\)，\(x\) 为前 \(k\) 个方程组的解，有
\[x=x_0+tM \text{ } (t \in \mathbb{Z}) \]代入原方程，有
\[x_0+tM \equiv a_k \pmod{m_k} \]移项得
\[Mt\equiv a_k-x_0 \pmod{m_k} \]变为线性同余方程，可以使用 Exgcd 求解出 \(t\) 的最小正整数解。
若该线性同余方程无解，则整个方程组无解。
将 \(t\) 代入原式求出 \(x\)，将 \(x_0 \leftarrow x\)，\(M \leftarrow \text{lcm}(M,m_k)\)。
这样就完成了一次合并。
依次将 \(n\) 个方程合并，就求出了整个方程组的解。
标签：frac,matrix,推导,pmod,Exgcd,Excrt,ax,gcd From： https://www.cnblogs.com/maniubi/p/18414376