最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

Exgcd（扩展欧几里得算法）

来源：博客园

其实挺简单。


(资料图)

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](https://www.cnblogs.com/xrlong/p/17073430.html)\)。

关键词： 同余方程 辗转相除法 于是我们