深入理解模运算与扩展欧几里得算法

核心逻辑与数学原理

模运算（Modular Arithmetic）是数论算法的基石。在计算机的补码架构下，必须确保所有的加、减、乘操作在每一步都及时取模，以防止整型溢出。

最大公约数（$GCD$）的核心基于欧几里得辗转相除法。其数学基础在于：若 $a = q \cdot b + r$，则 $\text{gcd}(a, b) = \text{gcd}(b, r)$。因为 $r = a \bmod b$，故 $\text{gcd}(a, b) = \text{gcd}(b, a \bmod b)$。当 $b = 0$ 时，$\text{gcd}(a, 0) = a$。其时间复杂度在最坏情况下（斐波那契数列相邻两项）为 $O(\log \min(a, b))$。

扩展欧几里得算法（$EXGCD$）用于求解裴蜀等式（Bézout's Identity）：

$$a \cdot x + b \cdot y = \text{gcd}(a, b)$$

该方程必然存在一组整数解 $(x, y)$。求解逻辑通过递归层层回溯：设 $b \cdot x' + (a \bmod b) \cdot y' = \text{gcd}(b, a \bmod b) = \text{gcd}(a, b)$。将 $a \bmod b = a - \lfloor \frac{a}{b} \rfloor \cdot b$ 带入等式变形得：

$$a \cdot y' + b \cdot (x' - \lfloor \frac{a}{b} \rfloor \cdot y') = \text{gcd}(a, b)$$

对比系数可得当前层的解：

$$\begin{cases} x = y' \\ y = x' - \lfloor \frac{a}{b} \rfloor \cdot y' \end{cases}$$

递归至终点 $b = 0$ 时，方程变为 $a \cdot x + 0 \cdot y = a$，此时解为 $x = 1, y = 0$。通过回溯即可得到原方程的一组特解 $(x_0, y_0)$。

算法推导与状态设计

对于更一般的线性同余方程（或二元一次不定方程）：

$$a \cdot x + b \cdot y = c$$

方程有解的充要条件是 $\text{gcd}(a, b) \mid c$（即 $c$ 是 $\text{gcd}(a, b)$ 的整数倍）。若不满足，直接判定无解。

若有解，先用 $EXGCD$ 求出 $a \cdot x_0 + b \cdot y_0 = \text{gcd}(a, b)$ 的一组特解 $(x_0, y_0)$。然后将等式两边同时乘以 $\frac{c}{\text{gcd}(a, b)}$，得到原方程的一组特解：

$$\begin{cases} X_0 = x_0 \cdot \frac{c}{\text{gcd}(a, b)} \\ Y_0 = y_0 \cdot \frac{c}{\text{gcd}(a, b)} \end{cases}$$

该方程的通解结构为：

$$\begin{cases} x = X_0 + k \cdot \frac{b}{\text{gcd}(a, b)} \\ y = Y_0 - k \cdot \frac{a}{\text{gcd}(a, b)} \end{cases} \quad (k \in \mathbb{Z})$$

在 NOIP 竞赛中，通常要求输出 $x$ 的最小正整数解。令 $g = \text{gcd}(a, b)$，步长 $t = \frac{b}{g}$。最小正整数解的修正公式为：

$$x_{\min} = (X_0 \bmod t + t) \bmod t$$

若要求此时对应的 $y$，直接带入原方程 $y = \frac{c - a \cdot x_{\min}}{b}$ 求解即可。

C++ 标准源码

#include <iostream>

// 扩展欧几里得算法，返回 gcd(a, b) 并通过引用更新 x 和 y
long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1; // 必须先做整除再做乘法，防止改变运算优先级
    return g;
}

// 求解 a * x + b * y = c 的最小正整数解 x
bool solve(long long a, long long b, long long c, long long &x, long long &y, long long &g) {
    g = exgcd(a, b, x, y);
    if (c % g != 0) return false; // 裴蜀定理条件检查，无法整除则无解

    long long t = b / g;
    x = x * (c / g); // 求出特解，注意此处存在中间结果溢出 long long 的风险（通常评测数据会限制范围）
    x = (x % t + t) % t; // 强制映射到 [0, t-1] 范围
    if (x == 0) x += t;  // 若要求严格正整数，0 需加上步长

    y = (c - a * x) / b; // 算出对应的 y
    return true;
}

int main() {
    // 优化标准输入输出流，切断与 stdin/stdout 的同步，提升 IO 效率
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long a, b, c;
    if (std::cin >> a >> b >> c) {
        long long x = 0, y = 0, g = 0;
        if (solve(a, b, c, x, y, g)) {
            std::cout << x << " " << y << "\n";
        } else {
            std::cout << "-1\n";
        }
    }
    return 0;
}

NOIP 实战避坑指南

模运算下减法的负数陷阱 在处理形如 $(a - b) \bmod m$ 的运算时，若 $a < b$，C++ 的 % 运算符会返回负数结果（例如 -3 % 5 = -3）。在数论题中这会导致索引越界或逻辑错误。必须写成：
```
long long ans = ((a - b) % m + m) % m;
```
exgcd 溢出与乘法中间结果爆 long long 当 $a, b, c$ 接近 $10^{18}$ 且满足 $\text{gcd}(a, b) = 1$ 时，执行 x = x * (c / g) 极易爆出 long long 的表示范围（产生整数溢出截断）。在必要时，必须使用 __int128_t 作为中间变量承载乘法运算，最后再模回目标范围。

经典 NOIP/洛谷真题

1. 洛谷 P1516 青蛙的约会

题意描述：两只青蛙在一条维度为 $L$ 的环形跑道上。青蛙 A 初始在 $x$，每次跳跃 $m$ 米；青蛙 B 初始在 $y$，每次跳跃 $n$ 米。问两只青蛙跳跃多少次（设为 $t$）后能相遇。
问题本质：列出位移同余方程：$x + m \cdot t \equiv y + n \cdot t \pmod L$。
核心解题思路：移项变形为 $(m - n) \cdot t + L \cdot k = y - x$。令 $a = m - n, b = L, c = y - x$，方程转化为标准的 $a \cdot t + b \cdot k = c$ 形式。应用 exgcd 求解 $t$ 的最小正整数解。注意若 $a < 0$，可将 $a$ 和 $c$ 取相反数转化为正数处理。

2. 洛谷 P1082 同余方程（NOIP 2012 提高组）

题意描述：求关于 $x$ 的同余方程 $a \cdot x \equiv 1 \pmod b$ 的最小正整数解。题目保证 $a$ 与 $b$ 互质。
问题本质：求 $a$ 在模 $b$ 意义下的乘法逆元。
核心解题思路：将同余方程转化为不定方程 $a \cdot x - b \cdot y = 1$。引入负号归纳为 $a \cdot x + b \cdot Y = 1$（其中 $Y = -y$）。直接调用 exgcd(a, b, x, Y)，求得的 $x$ 经过 (x % b + b) % b 修正后即为答案。