bdfz 2025 winter day1
GCD
GCD CRT 逆元
扩展欧几里得算法（Exgcd）用于求解方程 ax + by = \gcd(a, b) 的整数解 x 和 y，同时返回 a 和 b 的最大公约数。以下是代码的逐层解释：
递归终止条件
当 b = 0 时，方程为 a \cdot 1 + 0 \cdot 0 = a，此时：
-
x = 1, y = 0
-
直接返回 a（最大公约数）
递归过程
- 递归调用：计算 \gcd(b, a \% b)，得到解 x' 和 y'，满足：
b \cdot x' + (a \% b) \cdot y' = \gcd(b, a \% b)
根据欧几里得算法，\gcd(a, b) = \gcd(b, a \% b)。
- 转换解：将递归结果的解 x' 和 y' 转换为当前层的解 x 和 y。利用 a \% b = a - \lfloor a/b \rfloor \cdot b，原方程可重写为：
a \cdot y' + b \cdot (x' - \lfloor a/b \rfloor \cdot y') = \gcd(a, b)
因此：
-
x = y'
-
y = x' - \lfloor a/b \rfloor \cdot y'
代码步骤
-
保存递归前的 x：
int t = x（此时 x = x'）。 -
更新 x：
x = y（将 x 设为 y'）。 -
更新 y：
y = t - (a / b) * y（计算 y = x' - \lfloor a/b \rfloor \cdot y'）。
示例分析
以 a = 30, b = 12 为例：
-
递归至 \gcd(6, 0)，返回 x = 1, y = 0, \gcd = 6。
-
回溯到 \gcd(12, 6)，计算 x = 0, y = 1，满足 12 \cdot 0 + 6 \cdot 1 = 6。
-
回溯到 \gcd(30, 12)，计算 x = 1, y = -2，满足 30 \cdot 1 + 12 \cdot (-2) = 6。
总结
代码通过递归分解问题，逐步缩小规模。每次递归后，利用子问题的解 x' 和 y' 推导当前层的解 x 和 y，最终得到满足 ax + by = \gcd(a, b) 的整数解。
