数论：从提高组到提高组，这是不是一种的？
摘要：说明 最近可爱的 MGJ 连上了七天的数论课，然后她写了一篇提高组数论的合集。 由于篇幅原因，大部分例题不放代码。 此文章部分参考他人文章或借他人文章进行优化，链接如下： https:www.luogu.com.cnproblems
说明
最近可爱的 MGJ 连上了七天的数论课，然后她写了一篇提高组数论的合集。
由于篇幅原因，大部分例题不放代码。
此文章部分参考他人文章或借他人文章进行优化，链接如下：
https://www.luogu.com.cn/problem/solution/P5656；
https://www.luogu.com.cn/article/fcv6pwn2；
https://www.luogu.com.cn/article/n6if1g3y。
更新日志：
2026.3.4 22:35：更新扩展欧几里得（Exgcd）；
2026.3.5：更新乘法逆元；
2026.3.7：更新欧拉函数；
2026.3.8-3.9：更新中国剩余定理（CRT）；
2026.3.9-3.10：更新欧拉定理；
2026.3.11：更新小步大步算法（BSGS）；
2026.3.11 21:36：完善所有内容，整改错别字。
本文耗时 \(7\) 天在每天课余时间抽空写完，作者写文章不易，如有不当之处敬请谅解（可以私信作者）。
扩展欧几里得（Exgcd）
Part 0：前置知识
基础数学（四则运算，符号定义等）；
欧几里得定理：\(\gcd(a, b) = \gcd(b,\ a \bmod b)\)；
裴蜀定理。
Part 1：扩展欧几里得的定义
扩展欧几里得是一个算法，一般解决如下核心问题：
给定两个整数 \(a, b\)，找到整数 \(x, y\) 满足：
\[ax + by = \gcd(a, b)
\]
这个方程叫做裴蜀方程（Bézout's identity）。
它在信息学竞赛中有着广泛应用，如求解一次不定方程或同余方程。
Part 2：裴蜀方程的求解
我们使用递归推导。
我们对 \(ax + by = \gcd(a, b)\) 用一次欧几里得定理，得：
\[bx_1 + (a \bmod b)y_1 = \gcd(b,\ a \bmod b)
\]
将 \(a \bmod b\) 转化为 \(a - b \cdot \left\lfloor \frac{a}{b} \right \rfloor\)，得：
\[ax + by = bx_1 + \left(a - b \cdot \left\lfloor \frac{a}{b} \right \rfloor\right)y_1 = bx_1 + ay_1 - b \cdot \left\lfloor \frac{a}{b} \right \rfloor y_1 = ay_1 + b\left(x_1 - \left\lfloor \frac{a}{b} \right \rfloor y_1\right)
\]
与原式比较，得到一组特解：
\[\begin{cases} x = y_1 \\ y = x_1 - \left\lfloor \frac{a}{b} \right \rfloor y_1 \end{cases}
\]
于是，我们找到了上层 \(x, y\) 和本层 \(x_1, y_1\) 的关系。
最终当 \(b = 0\) 时，\(\gcd(a, 0) = a\)，方程变为 \(ax + 0y = a\)，显然得到一组解：\(x = 1\)，\(y = 0\)。
注意：
信息学大忌：在 \(b = 0\) 时耍帅把 \(y\) 随便写（如 \(114514\)），因为每一层递归时 \(x, y\) 都会变化。当递归次数足够多时，\(x, y\) 将会超出变量范围或产生某些其他问题。
下面给出两种模板代码，第一种好理解但代码较长（也长不了多少），新手建议使用第一种：
Code 1：
ll Exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1, y = 0;
return a;
}
ll d = Exgcd(b, a % b, x, y), tmp = x;
x = y, y = tmp - (a / b) * y;
return d;
}
Code 2：
ll Exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1, y = 0;
return a;
}
ll d = Exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
Part 3：扩展欧几里得的应用
3.1：解不定方程
常见问题：求不定方程 \(ax + by = c\) 的一组解。