数论：从提高组到提高组

说明

最近可爱的 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：

1. ll Exgcd(ll a, ll b, ll &x, ll &y) {
2.   if (!b) {
3.     x = 1, y = 0;
4.     return a;
5.   }
6.   ll d = Exgcd(b, a % b, x, y), tmp = x;
7.   x = y, y = tmp - (a / b) * y;
8.   return d;
9. }

复制代码

Code 2：

1. ll Exgcd(ll a, ll b, ll &x, ll &y) {
2.   if (!b) {
3.     x = 1, y = 0;
4.     return a;
5.   }
6.   ll d = Exgcd(b, a % b, y, x);
7.   y -= a / b * x;
8.   return d;
9. }

复制代码

Part 3：扩展欧几里得的应用

3.1：解不定方程

常见问题：求不定方程 \(ax + by = c\) 的一组解。
首先，先使用裴蜀定理判断是否有解：由裴蜀定理得 \(\gcd(a, b) \mid (ax + by)\)，故 \(\gcd(a, b) \nmid c\) 时不定方程无解。
然后，用 Exgcd 求出 \(ax + by = \gcd(a, b)\) 的一组整数特解 \(x_0, y_0\)。那么有：

\[ax_0 + by_0 = \gcd(a, b)\]
两边同乘 \(\cfrac{c}{\gcd(a, b)}\)，得：

\[a\cfrac{cx_0}{\gcd(a, b)} + b\cfrac{cy_0}{\gcd(a, b)} = c\]
与原式比较，可以得到一组特解：

\[\begin{cases} x_1 = \cfrac{cx_0}{\gcd(a, b)} \\ y_1 = \cfrac{cy_0}{\gcd(a, b)} \end{cases}\]
有了特解，那么就可以推导通解了。
显然有：

\[\begin{cases} ax_0 + by_0 = c \\ ax + by = c \end{cases}\]
令 \(\Delta x = x - x_0\)，\(\Delta y = y - y_0\)。
则：

\[a(x_0 + \Delta x) + b(y_0 + \Delta y) = c\]
展开，得：

\[ax_0 + a\Delta x + by_0 + b\Delta y = c\]
又 \(ax_0 + by_0 = c\)，则：

\[a\Delta x + b\Delta y = 0\]
通过各种方法，解得：

\[\begin{cases} \Delta x = k \cdot \cfrac{b}{\gcd(a, b)} \\ \Delta y = -k \cdot \cfrac{a}{\gcd(a, b)} \end{cases}\]
于是，我们得到通解形式：

\[\begin{cases} x = x_0 + k \cdot \cfrac{b}{\gcd(a, b)} \\ y = y_0 - k \cdot \cfrac{a}{\gcd(a, b)} \end{cases}\]
其中 \(k \in \mathbb{Z}\)。
我们还可以推导出，如果要求最小非负整数解，可以提前将系数 \(a, b\) 都除以 \(\gcd(a, b)\)。
3.2：解同余方程

常见问题：解形如 \(ax \equiv c \pmod b\) 的同余方程。
考虑将此方程尽可能写成 \(ax + by = c\) 的形式：

\[\because ax \equiv c \pmod b \therefore ax \bmod b = c \bmod b \because by \bmod b = 0\ \ (y \in \mathbb{N}) \therefore ax \bmod b + by \bmod b = c \bmod b \therefore ax + by \equiv c \pmod b\]
于是就变成了不定方程的形式。
Part 4：例题

P1082 [NOIP 2012 提高组] 同余方程 / P2613【模板】有理数取余

两题均为套模板题。
讲解几个需要注意的点：

• 在 P1082 中，为了避免 \(x_0\) 为负数，我们需要先 \(x \to x \bmod b\)，再将 \(x \to x + b\)。但这可能并不是最小整数解，所以我们需要调整为 \(x' = (x_0 \bmod b + b) \bmod b\)；
  
• 在 P2613 中，非负整数 \(a, b\) 的范围达到 \(10 ^{10001}\)，所以需要结合快读一边读入一边取模；
  
• 在 P2613 中，需要判断无解情况。
  

P1516 青蛙的约会

如果他们相遇，他们初始的位置坐标之差和跳的距离应该在模 \(l\) 下同余。
令 \(k\) 为跳的次数，则 \((n - m)k \equiv x - y \pmod l\)。
套模板即可，注意 \(n - m\) 和 \(x - y\) 可能为负数和无解情况。
P5656 【模板】二元一次不定方程 (exgcd)

模板简单，模板题不一定简单。因为此题细节很多，需要一一处理。
下面所有变量源于 Part 3 的应用 1。
那么我们先求最小值。首先，肯定的是用 Exgcd 求出一组特解 \(x_0, y_0\)，那么显然 \(x, y\) 最小正整数解为 \(x_{\min} = (x_0 \bmod \Delta x + \Delta x) \bmod \Delta x\)，\(y_{\min} = (y_0 \bmod \Delta y + \Delta y) \bmod \Delta y\)（读者可以简单证明）。
然后就可以求最大值了。最大值怎么求？很显然，对于 \(x_{\min}, y_{\min}\)，有 \(ax_{\min} + by_{\max} = c\) 和 \(ax_{\max} + by_{\min} = c\)。那么 \(y_{\max} = \cfrac{c - ax_{\min}}{b}\)，\(x_{\max} = \cfrac{c - by_{\min}}{a}\)。
你以为这就结束了？我们还没有处理没有正整数解的情况。当我们限制 \(x, y > 0\) 时，可以推导出 \(k\) 的取值范围，当 \(k\) 的下界大于上界时就没有正整数解。
Code：
[code]#include using namespace std;using ll = long long;using ull = unsigned long long;const int kMaxN = 2e5 + 10;ll a, b, c, d, x, y, dx, dy, m, n, xmn, xmx, ymn, ymx;ll Exgcd(ll a, ll b, ll &x, ll &y) {  if (!b) {    x = 1, y = 0;    return a;  }  ll res = Exgcd(b, a % b, y, x);  y -= a / b * x;  return res;}int main() {  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);  int t;  for (cin >> t; t; -- t) {    cin >> a >> b >> c;    d = Exgcd(a, b, x, y);    if (c % d) {      cout  n) {      cout