一、引言
在信息学奥赛 CSP-J 的备考中，数学知识是不可或缺的一部分。线性同余方程 ax ≡ b (mod m) 是一个常见且重要的考点。
二、知识点详解
（一）求解步骤
1. 首先，使用扩展欧几里得算法求出 a 和 m 的最大公约数 d 以及一组整数 x 和 y ，使得 ax + my = d 。
- 学习扩展欧几里得算法时，要理解其原理是通过递归不断缩小问题规模，直到找到基本情况。
- 反复练习手动计算过程，掌握每一步的推导。
2. 若 d 不能整除 b ，则方程无解。
3. 若 d 能整除 b ，则方程有解。将扩展欧几里得算法求得的 x 乘以 b/d ，得到一个特解 x₀ 。
（二）通解表示
方程的通解可以表示为 x = x₀ + k(m/d) ，其中 k 为整数。
三、无解情况的判断条件
当 a 和 m 的最大公约数 d 不能整除 b 时，方程 ax ≡ b (mod m) 无解。
四、实际问题建模方法
在实际问题中，将相关的数量关系转化为线性同余方程的形式。例如，在周期性问题、分组问题等中，常常可以通过分析余数来建立方程。
五、总结
线性同余方程的求解需要熟练掌握扩展欧几里得算法，准确判断无解情况，并能够将实际问题有效地建模为线性同余方程进行求解。通过大量的练习和总结，能够更好地应对这一考点。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
