EXGCD

扩展欧几里得算法（ExGCD）

常见考查场景：

• 求解线性不定方程（Diophantine Equation）。
• 解决线性同余方程。
• 在中国剩余定理（CRT）中合并方程时计算逆元。
• 需要找出贝祖系数来表示 gcd 的线性组合。

典型题目与分析

1. 线性不定方程求解

   • 题目描述：给定 a、b 和 c，判断方程$ax+by=c$是否有整数解，并输出其中一组解。
   • 考查点：先用 exgcd 求 $\gcd (a,b)$ ，再判断 c 是否为其倍数。
   • 分析：如果 ccc 能被 $\gcd (a,b)$ 整除，则将 exgcd 得到的基本解乘以$c/\gcd (a,b)$ 即为解。重点在于参数的调整。

2. 求解模线性方程

   • 题目描述：求解同余方程$ax\equiv c(\mathrm{mod}m)$ 的所有解。
   • 考查点：判断 $\gcd (a,m)$ 是否整除 c ；若可解，利用 exgcd 求出基本解，再写出通解形式。
   • 分析：考查对同余方程解的参数描述和解集刻画。

3. 求最小非负解

   • 题目描述：在方程 $x+by=c$ 或同余 $ax\equiv b(\mathrm{mod}m)$ 中，要求输出满足某个变量最小非负的解。
   • 考查点：得到基本解后，通过加减模的周期（或平移参数）调整到非负区域。
   • 分析：需要灵活应用 exgcd 得到的通解形式，并利用模运算找到最优解。

4. 鸡兔同笼（或硬币问题）

   • 题目描述：经典问题：鸡和兔子总数和总脚数已知，求鸡和兔子的数量。
   • 考查点：将问题转化为 $2x+4y=n$ 的线性方程，并用 exgcd 求解。
   • 分析：先判断方程可解性，然后找到基本解，再根据问题约束（非负整数）筛选合适的解。

5. 中国剩余定理（CRT）的实现

   • 题目描述：给定一组同余方程，求一个最小正整数满足所有方程。
   • 考查点：在每一步合并两个同余方程时，用 exgcd 计算模逆元来构造合并公式。
   • 分析：考查对 exgcd 在 CRT 算法中作用的理解，重点在于正确处理模数不互质情况（通常题目保证互质）。