在 CSP-S 备考的最后一个月冲刺阶段，数论进阶部分是重点之一。其中，扩展欧几里得算法、线性同余方程以及模逆元的求解尤为重要。
一、扩展欧几里得算法求解 ax + by = gcd(a, b) 的通解
扩展欧几里得算法不仅能求出两个数的最大公约数，还能同时得到满足贝祖等式 ax + by = gcd(a, b) 的整数解 x 和 y。
其基本思想是通过递归不断缩小问题规模。假设我们已经求出 gcd(b, a mod b) 以及对应的系数 x’ 和 y’，那么可以得到 x 和 y 的关系式：x = y’ ，y = x’ - (a / b) * y’ 。
学习方法：
1. 理解其递归的本质，通过手动推导几组具体的例子来加深印象。
2. 多做练习题，熟练掌握在不同数据规模下的应用。
二、线性同余方程 ax ≡ b (mod m) 的解存在条件及求解步骤
解存在的条件是 gcd(a, m) 整除 b。
求解步骤通常包括：
1. 首先判断解是否存在。
2. 若存在，利用扩展欧几里得算法求出一组特解 x0 和 y0，使得 ax0 + my0 = gcd(a, m) 。
3. 将特解乘以 b / gcd(a, m) 得到原方程的特解 x1 = x0 * (b / gcd(a, m)) 。
4. 则通解为 x = x1 + k * (m / gcd(a, m)) ，其中 k 为整数。
学习要点：
1. 牢记解存在的条件，这是求解的前提。
2. 反复练习求解步骤，注意计算的准确性。
三、模逆元的两种计算方法（费马小定理与扩展欧几里得）
费马小定理：当 m 为质数时，若 a 和 m 互质，则 a^(m - 1) ≡ 1 (mod m) ，所以 a 的模逆元为 a^(m - 2) (mod m) 。可以通过快速幂算法高效计算。
扩展欧几里得算法：通过求解 ax + my = 1 ，得到的 x 即为 a 关于 m 的模逆元。
学习建议：
1. 对于费马小定理，要理解其原理，并熟练掌握快速幂的实现。
2. 对于扩展欧几里得算法求模逆元，要能将其与求解线性方程的思路联系起来。
总之，在最后的冲刺阶段，要重点复习这些数论进阶的知识点，通过大量的练习来巩固，提高解题的速度和准确性，为 CSP-S 考试做好充分准备。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
