信奥赛C++数论专题：从同余到裴蜀定理实战

1. 课程概述与目标定位

信奥赛C++提高组选手在备战过程中，数论知识始终是区分选手水平的关键分水岭。本次专题聚焦从同余理论到分数模运算的核心知识链，特别针对裴蜀定理及其衍生算法进行深度剖析。这个知识模块在近年CSP-S/S复赛中出现频率高达37%，是解决数论难题的基础工具包。

作为竞赛教练，我发现在实际教学中，许多选手能背诵定理却无法灵活运用，问题往往出在三个层面：

1. 对定理成立条件的敏感性不足
2. 算法实现时的边界处理缺失
3. 问题转化时的思维定式

本专题将通过"理论推导+算法实现+案例解剖"的三段式教学，带大家打通数论学习的任督二脉。以下是课程核心路线图：

code复制同余基础 → 裴蜀定理 → 扩展欧几里得 → 乘法逆元 → 分数模运算

2. 知识体系构建

2.1 同余理论基石

同余概念是数论大厦的基石，在竞赛中常见的应用形式包括：

• 模运算性质：(a±b)%m = (a%m ± b%m)%m
• 同余方程：ax ≡ b (mod m)的解法
• 中国剩余定理的联合应用

特别要注意负数的模运算处理，这是新手常踩的坑。例如在C++中：

cpp复制int mod = 5;
int a = -7;
cout << (a % mod + mod) % mod;  // 输出3，正确结果

2.2 裴蜀定理深度解析

定理内容：对于任意整数a,b，存在整数x,y使得ax+by=gcd(a,b)。这个看似简单的结论却蕴含着强大的应用价值：

1. 判定方程有解性：不定方程ax+by=c有整数解当且仅当gcd(a,b)|c
2. 构造通解公式：若(x0,y0)是一组特解，则通解为：

   code复制x = x0 + k*(b/gcd(a,b))
   y = y0 - k*(a/gcd(a,b))
   

3. 推广到多元情形：n元线性方程a1x1+...+anxn=c有解⇔gcd(a1,...,an)|c

竞赛中常见的伪装形式包括：

• 将问题转化为求多个数的最大公约数
• 隐含的系数提取问题
• 与其他数论知识结合的综合题

3. 算法实现精要

3.1 扩展欧几里得算法模板

标准欧几里得算法只能求出gcd，而扩展版