算法学习笔记(8)：拓展欧几里得

Question

如题所述

Answer 1

欢迎来到算法探索的深入之旅，今天我们将聚焦在欧几里得算法的拓展——拓展欧几里得，一个在数论中极具实用价值的工具。首先，让我们回顾一下基础的辗转相除法，代码简洁明了：

int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a%b); }

这个算法的原理在于，通过反复取余数，逐步揭示两个数的最大公因数。不妨设想（稍后将详细解释），设 a 为被除数，b 为除数，那么商 c 和余数 d 可以表示为 c = a/b，d = a % b。由于 a 和 b 都是 gcd(a, b) 的倍数，所以 gcd(a, b) 也是 d 的倍数。这样反复递归，直至 b 为零，a 就是最终答案。

在实现辗转相除法时，我们常常会考虑数的大小关系，比如在 gcd 函数开头加 if (a < b) swap(a, b);，但其实这一步并非必要。因为如果 a 小于 b，函数会自然地进行一次交换，不必额外处理。

拓展欧几里得算法的出现，让我们在求解不定方程 ax + by = gcd(a, b) 时有了新手段。关键在于，我们不仅能找到一组解，还能推导出所有解的通式。例如，对于 a = 13, b = 11，我们可以逐步推导出通解 x = 11k + 4 和 y = 13k - 4，其中 k 为任意整数。

在实际应用中，比如洛谷P1082题目，我们需要解决 ax ≡ b (mod n) 的最小正整数解。这时，由于 a 和 n 互质，通解简化为 x = b / a。但要注意，C++的模运算可能产生负数，所以需要加上 b 再取模，确保结果为正。

int main() { int a, b, x, y; cin >> a >> b; int gcd_value = exgcd(a, b, x, y); x = (x % b + b) % b; cout << x; return 0; }

通过扩展欧几里得算法，我们不仅深化了对基础算法的理解，还学会了如何在实际问题中灵活运用，这在求解同余方程等数论问题中显得尤为重要。继续探索，让我们在算法的海洋中寻找更多宝藏！