一、擴展歐幾里得算法

1、裴蜀定理

對于任意正整數 $a$，$b$，那么一定存在非零整數 $x$，$y$，使得 $ax+by=exgcd(a,b)$

2、過程模擬

例如求 $gcd(a,b)$

$?$當 $b=0$ 時，則可以直接返回 $a$ 的值，即最大公約數，推理如下：

根據公式$ax+by=exgcd(a,b)$，得：

$a\times x+0\times y=a$

$?a\times x=a$

$?x=1$

$?y=0$

$?$當 $b\ne 0$ 時，求得擴展歐幾里得算法$exgcd(b,a\%b,y,x)$，推理如下：

$by+(a$ $mod$ $b)x=exgcd(a,b)$

$?a$ $mod$ $b=a??\frac{a}{b}?b$

$?by+(a??\frac{a}{b}?b)x=exgcd(a,b)$

$?ax+b(y??\frac{a}{b}?x)=exgcd(a,b)$

3、代碼模板

// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{if (!b){x = 1; y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= (a/b) * x;return d;
}

Acwing-擴展歐幾里得算法

二、線性同余方程

1、定義

給定 $n$ 組數據 $a_i$，$b_i$，$m_i$，對于每組數求出一個 $x_i$，使其滿足 $a_i\times x_i\equiv b_i(mod$ $m_i)$。

2、模擬過程

設 $a=2$，$b=3$，$m=6$，此時以上并不滿足條件。

設 $a=4$，$b=3$，$m=5$，要使 $4x\%5=3$，所以$x=?3$或$x=2$

3、結論證明

$a\times x\equiv b(mod$ $m)$

$?$$?y\in Z$，使得$ax=my+b$

$?ax?my=b$

$?y^{\prime }=?y$

$?ax+m{y}^{\prime }=gcd(a,m)$（條件：$gcd(a,m)|b$）