其實挺簡單。
GCD（輾轉相除法）
定理：
\[\gcd(a , b) = \gcd(b , a \bmod 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\not= 0\) 時：
\[\text{設 } ax_1+by_1=gcd(a,b)=gcd(b,a \bmod b)=bx_2+(a\bmod b)y_2
\]
\[\because a \bmod b = a - a / b * b
\]
\[\therefore ax_1 + by_1 = bx_2+ (a - a / b * b) y_2
\]
\[\therefore ax_1 + by_1 = bx_2 + ay_2 - a / b * by_2
\]
\[\therefore ax_1 + by_1 = ay_2 + bx_2 - b * a/b * y_2
\]
\[\therefore ax_1 + by_1 = ay_2 + b (x_2 - a / b * y_2)
\]
\[\text{解得 } x_1 = y_2 , y_1 = x_2 - a / b * y_2
\]
得證
通過這個證明，我們發現可以在維護 \(\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\)。
浙公網安備 33010602011771號