信奥赛C++提高组数论专题：同余与分数模运算

信奥赛C++提高组数论专题：同余与分数模运算

课程目标

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

---

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

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

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