Exgcd（扩展欧几里得算法）
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
其实挺简单。
GCD（辗转相除法）
定理：
\[\gcd(a , b) = \gcd(b , a \% b)
\]
证明：
\[\text{设 } a = kb + r \text{ ，则 } r = a \bmod b
\]
\[\text{若 } c \text{ 是 } a,b \text{ 的一个公约数，则 } c \mid a,c \mid b
\]
\[\because r = a - kb
\]
\[\therefore c \mid r
\]
\[\therefore c \text{ 是 } b,a \bmod b \text{ 的公约数}
\]
\[\text{同理，若 } d \text{ 是 } b,a \bmod b \text{ 的公约数，则 } d \mid b,d \mid r
\]
\[\because a = kb + r
\]
\[\therefore d \mid a
\]
\[\therefore d \text{ 也是 } a,b \text{ 的公约数}
\]
\[\therefore a,b \text{ 和 } b,a \bmod b \text{ 的公约数是一样的，其最大公约数也必然相等，证毕}
\]
code（递归式）:
int gcd(int a,int b){
return (b==0)?a:gcd(b,a%b);
}
EXGCD（扩展欧几里得）
裴蜀定理：
\[\forall a,b \in Z \text{ , } \exists x,y \in Z
\]
满足
\[ax+by=\gcd(x,y)
\]
证明（类似递归）：
当 b=0 时:
\[\gcd(a,b)=a \text{ ，此时 } x=1 , y=0
\]
当 b!=0 时：
\[\text{设 } ax1+by1=gcd(a,b)=gcd(b,a%b)=bx2+(a%b)y2
\]
\[\because a \bmod b = a - a / b * b
\]
\[\therefore ax1 + by1 = bx 2+ (a - a / b * b) y2
\]
\[\therefore ax1 + by1 = bx2 + ay2 - a / b * by2
\]
\[\therefore ax1 + by1 = ay2 + bx2 - b * a/b * y2
\]
\[\therefore ax1 + by1 = ay2 + b (x2 - a / b * y2)
\]
\[\text{解得 } x1 = y2 , y1 = x2 - a / b * y2
\]
用类似递归的方法即可得证。
通过这个证明，我们发现可以在维护 \(\gcd\) 时同时维护 \(x,y\) 的值。
code:
int exgcd(int a,int b,int &x,int &y){
if(b==0) {x=1,y=0;return a;}
else{
int ans=exgcd(b,a%b,y,x);
y-=a/b*x;
return ans;
}
}
用途（1，2为基本用途）：
1.
首先看怎么解
\[ax+by=c
\]
这类方程
首先：若 \(\gcd(a,b) \nmid c\) 可以知道原方程没有整数解（等式左右因数不相等，显然无整数解。
所以我们将原方程左边 \(\times \gcd(a,b) / c\) ,然后通过解 \(ax_0+by_0=\gcd(a,b)\) 解得 \(x_0,y_0\) ，最后将 \(x_0,y_0\) 乘上 \(c / \gcd(a,b)\) 解出原方程的一组解 \(x_1,y_1\).
显然，我们将 \(x_1 + b / \gcd(a,b) * t,y_1 - a/ \gcd(a,b) * t\) （ \(t\) 为任意整数）即可得出所有解。
2.
然后，我们再来看下同余方程
\[ax\equiv l \pmod{m}
\]
其实稍加转化，就得到了
\[ax+my=l
\]
解这个方程即可，注意 \(x\) 的特殊要求。
3.
最后，我们来看一下同余方程组
\[\begin{cases} x\equiv a_1\pmod{m_1} \\ x\equiv a_2\pmod{m_2} \\ ... \\ x\equiv a_n\pmod{m_n}\end{cases}
\]
若所有 \(m\) 互质，可以用 \(crt\) 求解。
这里主要说不互质的用 \(exgcd\) 解法
首先看第一二个式子：
\[\begin{cases} x\equiv a_1\pmod{m_1} \\ x\equiv a_2\pmod{m_2}\end{cases}
\]
变形得到：
\[\begin{cases} x = a_1 + m_1k_1 \\ x = a_2 + m_2k_2\end{cases}
\]
\[\therefore a_1+m_1k_1=a_2+m_2k_2
\]
整理：
\[m_1k_1-m_2k_2=a_2-a_1
\]
运用 \(exgcd\) 解得 \(k_1\) 的一组解：
\[k_1=r
\]
\[\therefore k_1 \text{ 的通解为 } k_1=r+\frac{m_2}{\gcd(m_1,m_2)} \times t \mid t \in Z
\]
将上式带入 \(x = a_1 + m_1k_1\) 得：
\[x=a_1+m_1r+\frac{m_1m_2}{\gcd(m_1,m_2)}\times t
\]
\[\because \operatorname{lcm(m_1,m_2)}=\frac{m_1m_2}{\gcd(m_1,m_2)}
\]
\[\therefore x=a_1+m_1r+\operatorname{lcm(m_1,m_2)}\times t
\]
变形得到：
\[x\equiv a_1+m_1r\pmod{\operatorname{lcm(m_1,m_2)}}
\]
于是我们就成功将两个同余方程化简成了一个。
同理化简下去直到一个，求解即可。
例题
——后来 jijidawang 说这就是 \(excrt\)。