信奥赛C++提高组csp-s之数论基础专题课：从同余到分数模运算1(知识地图：同余、裴蜀定理、扩展欧几里得、乘法逆元、分数模运算)

信奥赛C++提高组csp-s之数论基础专题课：从同余到分数模运算1(知识地图：同余、裴蜀定理、扩展欧几里得、乘法逆元、分数模运算)

课程目标

1. 理清脉络：理解同余、裴蜀定理、扩展欧几里得、乘法逆元、分数模运算之间的逻辑关系。
2. 掌握核心：熟练运用扩展欧几里得算法求解不定方程及逆元。
3. 实战应用：能够解决相关的数论模板题和简单变式题。

第一部分：知识地图与衔接逻辑

这五个知识点可以看成是一条 “生产流水线”，最终目的是为了解决 “分数取模” 这个看似复杂的问题。

1. 起点：同余
   • 这是所有问题的背景。我们研究的世界不再是整数，而是 “模 m 的世界”。在这里，所有的数都只关心它除以 m 的余数。
   • 核心矛盾：在这个世界里，加法、减法、乘法都很好用，唯独 除法 不成立（例如