辗转相除法 & exGCD1

辗转相除法 & exGCD 本节主要介绍辗转相除法（欧几里得算法）和扩展欧几里得算法（exGCD），并讨论其在解二元一次不定方程中的应用。 1. 欧几里得算法（辗转相除法） 欧几里得算法是计算两个整数的最大公约数（Greatest Common Divisor，GCD）的经典算法。设 g 是 a 和 b 的最大公约数，那么 ax + by 一定也是 g 的倍数。如果 c 不是 g 的倍数，直接返回无解。因此，我们先考虑如何计算最大公约数gcd(a, b)。 欧几里得算法的关键在于递归地将问题规模减小。当 b = 0 时，gcd(a, b) = gcd(a, 0) = a。而 b ≠ 0 时，我们用 gcd(a, b) = gcd(a − b, b) 来减小问题规模。证明如下： * a, b 的公约数一定是 a − b, b 的公约数，不会遗漏。 * a − b, b 的公约数一定是 a, b 的公约数，不会新增。 于是得到 gcd(a, b) = gcd(a − b, b)。注意到 a mod b 相当于 a 减去若干次 b，所以 gcd(a, b) = gcd(a mod b, b)。 欧几里得算法的代码实现如下： ```c using ll = long long; ll GCD(ll a, ll b) { while (b != 0) { a %= b; swap(a, b); } return a; } ``` 2. 扩展欧几里得算法（exGCD） 扩展欧几里得算法是欧几里得算法的扩展，用于解二元一次不定方程 ax + by = c。假设 c 是 gcd(a, b) 的倍数，那么问题转化为如何解 ax + by = gcd(a, b)，然后给解乘上 c/gcd(a, b) 即可。 扩展欧几里得算法的关键在于将等式不断辗转相除 直到等式右边是 gcd(a, b)。具体流程如下： * 假设存在两个等式：ax1 + by1 = c1, ax2 + by2 = c2 * 可以得到：a(x1 − x2) + b(y1 − y2) = c1 − c2 * 等式也可以像整数一样加减乘除。 扩展欧几里得算法的代码实现如下： ```c using ll = long long; tuple<ll, ll, ll> exGCD(ll a, ll b) { // 1. 初始化 tuple<ll, ll, ll> equation[2] = {{1, 0, a}, {0, 1, b}}; int cnt = 0; while (get<2>(equation[1]) != 0) { // 2. 获取商 ll q = get<2>(equation[0]) / get<2>(equation[1]); // 3. 得到新的等式 equation[0] = { get<0>(equation[0]) - q * get<0>(equation[1]), get<1>(equation[0]) - q * get<1>(equation[1]), get<2>(equation[0]) - q * get<2>(equation[1]) }; swap(equation[0], equation[1]); } return equation[0]; } ``` 3. 应用：乘法逆元问题 扩展欧几里得算法也可以用于解决乘法逆元问题。给定一对互素的正整数 a 和 m，即 gcd(a, m) = 1。求一个整数 a−1 满足 aa−1 ≡ 0 mod m。 解法首先我们解不定方程 ax + my = 1。由于互素，一定存在合法解。现在等式左边等于 1，所以等式左边等于 1，所以在模 m 意义下一定也等于 1。由于 my 是 m 的倍数，所以在模 m 意义下等于 0。那么就可以得到 ax ≡ 1 mod m。让 a−1 = x 就是所求的逆元了。 辗转相除法和扩展欧几里得算法是计算最大公约数和解二元一次不定方程的重要工具。它们广泛应用于数论、代数和计算机科学等领域。