信奥赛C++数论基础：同余、逆元与模运算精解

1. 数论基础专题课概述

信奥赛C++提高组csp-s的数论基础专题课，是算法竞赛选手必须掌握的硬核内容。这套课程从同余概念出发，逐步深入到分数模运算，涵盖了竞赛中90%的数论考点。我在辅导学生备战信奥赛的五年中发现，数论题往往是区分选手水平的关键——能熟练运用这些知识的学生，在竞赛中至少能多解决2-3道压轴题。

这个专题最精妙之处在于知识点的递进关系：同余是基石，裴蜀定理搭建桥梁，扩展欧几里得算法实现具体计算，而乘法逆元和分数模运算则是竞赛中的高频应用点。去年省赛的压轴题"模意义下的方程求解"，就同时考察了扩展欧几里得和分数模运算的复合应用。

2. 同余概念深度解析

2.1 同余的定义与基本性质

同余概念最早出现在高斯1801年的《算术研究》中，定义非常简单却威力巨大：对于整数a,b和正整数m，如果m|(a-b)，就说a与b模m同余，记作a≡b(mod m)。这个看似简单的定义，却衍生出竞赛中无数精妙的解法。

在实际编程中，我们常用以下性质简化计算：

1. 加法封闭性：(a≡b且c≡d) ⇒ (a+c≡b+d)
2. 乘法封闭性：(a≡b且c≡d) ⇒ (a×c≡b×d)
3. 幂次可传递：a≡b ⇒ aⁿ≡bⁿ

重要提示：处理负数取模时，不同语言有不同实现。C++中(-7)%3=-1，而Python中(-7)%3=2。竞赛中通常要求结果在[0,m)区间，需要手动调整：

cpp复制int mod(int a, int m) {
    return (a % m + m) % m;
}

2.2 同余的应用场景

1. 循环节检测：在求解斐波那契数列模m的周期时，利用同余性质可以大幅减少计算量。例如Pisano周期问题。

2. 哈希冲突处理：设计哈希表时，利用同余关系实现二次探查法。

3. 随机数生成：线性同余生成器(LCG)的核心就是同余运算：

   cpp复制class LCG {
       uint64_t state;
   public:
       LCG(uint64_t seed) : state(seed) {}
       uint32_t next() {
           state = (state * 63641362238467