數(shù)論——?dú)W幾里得算法、裴蜀定理、擴(kuò)展歐幾里得算法
引入
最大公約數(shù)
最大公約數(shù)即為 Greatest Common Divisor，?？s寫(xiě)為 gcd。
一組整數(shù)的公約數(shù)，是指同時(shí)是這組數(shù)中每一個(gè)數(shù)的約數(shù)的數(shù)。\(\pm 1\) 是任意一組整數(shù)的公約數(shù)；
一組整數(shù)的最大公約數(shù)，是指所有公約數(shù)里面最大的一個(gè)。
特殊的，我們定義 \(\gcd(a, 0) = a\)。
最小公倍數(shù)
最小公倍數(shù)即為 Least Common Multiple，常縮寫(xiě)為 lcm。
一組整數(shù)的公倍數(shù)，是指同時(shí)是這組數(shù)中每一個(gè)數(shù)的倍數(shù)的數(shù)。\(0\) 是任意一組整數(shù)的公倍數(shù)；
一組整數(shù)的最小公倍數(shù)（Least Common Multiple, LCM），是指所有正的公倍數(shù)里面，最小的一個(gè)數(shù)。
互質(zhì)
如果兩個(gè)數(shù) \(a\) 和 \(b\) 滿足 \(\gcd(a, b) = 1\)，我們稱 \(a\) 和 \(b\) 互質(zhì)，記作 \(a\perp b\)。
歐幾里得算法
歐幾里得算法（Euclidean algorithm），是求解兩個(gè)數(shù)最大公約數(shù)的最常用的算法。
算法思想
\(\gcd(a, b) = \gcd(b, a \bmod b)\)
具體證明見(jiàn)：OI-Wiki。
代碼
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
因此也有遞歸寫(xiě)法：
int gcd(int a, int b) {
int tmp;
while (b != 0) tmp = a, a = b, b = tmp % b;
return a;
}
對(duì)于 C++14，我們可以使用 中的 __gcd(a,b) 函數(shù)來(lái)求最大公約數(shù)。
時(shí)間復(fù)雜度
在輸入為兩個(gè)長(zhǎng)為 \(n\) 的二進(jìn)制整數(shù)時(shí)，歐幾里得算法的時(shí)間復(fù)雜度為 \(O(n)\)；
換句話說(shuō)，在默認(rèn) \(a, b\) 同階的情況下，時(shí)間復(fù)雜度為 \(O(\log\max(a, b))\)。
歐幾里得算法的最劣時(shí)間復(fù)雜度情況是 \(\gcd(\operatorname{Fib}_{n + 1}, \operatorname{Fib}_n)\)，其時(shí)間復(fù)雜度為 \(O(n)\)；
但是，有 \(\gcd(\operatorname{Fib}_{n + 1}, \operatorname{Fib}_n) = \operatorname{Fib}_{\gcd(n + 1, n)}\)。
最小公倍數(shù)
計(jì)算
\(\gcd(a, b) \times \operatorname{lcm}(a, b) = a \times b\)。
要求兩個(gè)數(shù)的最小公倍數(shù)，先求出最大公約數(shù)即可。
證明
設(shè) \(a = p_1^{k_{a_1}}p_2^{k_{a_2}} \dots p_s^{k_{a_s}}\)，\(b = p_1^{k_{b_1}}p_2^{k_{b_2}} \dots p_s^{k_{b_s}}\)。
我們發(fā)現(xiàn)，對(duì)于 \(a\) 和 \(b\) 的情況，二者的最大公約數(shù)等于 \(p_1^{\min(k_{a_1}, k_{b_1})}p_2^{\min(k_{a_2}, k_{b_2})} \dots p_s^{\min(k_{a_s}, k_{b_s})}\)。
最小公倍數(shù)等于 \(p_1^{\max(k_{a_1}, k_{b_1})}p_2^{\max(k_{a_2}, k_{b_2})} \dots p_s^{\max(k_{a_s}, k_{b_s})}\)。
由于 \(k_a + k_b = \max(k_a, k_b) + \min(k_a, k_b)\)，
所以得到結(jié)論是 \(\gcd(a, b) \times \operatorname{lcm}(a, b) = a \times b\)。
裴蜀定理
定義
若 \(a\)、\(b\) 是不全為零的整數(shù)，則存在整數(shù) \(x\)、\(y\)，使得 \(ax + by = \gcd(a, b)\)。
推廣
若 \(A[1 \sim n]\) 是非零整數(shù)序列，則整數(shù)序列 \(X[1 \sim n]\) 一定滿足：
\(\displaystyle \sum_{i = 1}^n A_iX_i = k \times \gcd(A_1, A_2, \dots, A_n)\)，其中 \(k\) 為正整數(shù)。
擴(kuò)展歐幾里得算法
擴(kuò)展歐幾里得算法（Extended Euclidean algorithm，EXGCD），常用于求 \(ax + by = \gcd(a, b)\) 的一組可行解。
算法思路
對(duì)于 \(ax + by = \gcd(a, b)\)，考慮與歐幾里得算法相似的思路：
| 結(jié)論： | |
|---|---|
| 求一組解 \(x'\)、\(y'\)，使得 | \(bx' + (a \bmod b)y' = \gcd(b, a \bmod b)\) |
| （歐幾里得定理）\(\gcd(a, b) = \gcd(b, a \bmod b)\) | \(bx' + (a \bmod b)y' = \gcd(a, b)\) |
| （模運(yùn)算的定義）\(a \bmod b = a - \lfloor \dfrac{a} \rfloor \times b\) | \(bx' + (a - \lfloor \dfrac{a} \rfloor \times b)y' = \gcd(a, b)\) |
| 整理，得 | \(ay' + b(x' - \lfloor \dfrac{a} \rfloor \times y') = \gcd(a, b)\) |
我們要求一組解，使得 \(ax + by = \gcd(a, b)\)
因此有一組解為 \(\left\{\begin{array}{l} x = y' \\ y = x' - \lfloor \dfrac{a} \rfloor \times y'\end{array}\right.\)
其邊界值為 \(b = 0\)，這時(shí)有 \(ax = \gcd(a, 0) = a\)，既有 \(x = 1\)；為了方便起見(jiàn)，我們?nèi)?\(y = 0\)。
即：若 \(b = 0\)，則取 \(\left\{\begin{array}{l} x = 1 \\ y = 0\end{array}\right.\)
代碼
來(lái)自 OI-Wiki：
int Exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int d = Exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - (a / b) * y;
return d;
}
簡(jiǎn)化后可以寫(xiě)作：
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;
}
特解到通解
假設(shè)我們現(xiàn)在求出了一組特解 \(x_0\)、\(y_0\)，使得 \(ax_0 + by_0 = \gcd(a, b)\)
接下來(lái)：
可以看出 \(H\) 即是 \(a\) 的倍數(shù)，又是 \(b\) 的倍數(shù)，
所以 \(H = k \times \operatorname{lcm}(a, b)\)，其中 \(k\) 可以是任意整數(shù)。
即：\(\left\{\begin{array}{l} x = x_0 + k \times \dfrac{\operatorname{lcm}(a, b)}{a} \\ y = y_0 + k \times \dfrac{\operatorname{lcm}(a, b)}\end{array}\right.\). 其中 \(k \in \mathbb{Z}\).文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-710173.html
Reference
到了這里，關(guān)于數(shù)論——?dú)W幾里得算法、裴蜀定理、擴(kuò)展歐幾里得算法 學(xué)習(xí)筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
