【算法基础篇】（四十六）同余方程终极攻略：从基础转化到实战破解

前言

在算法竞赛的数论战场中，同余方程是绕不开的核心考点。它看似抽象难懂，实则是 “线性不定方程” 的另一种表现形式，只要掌握了转化技巧和求解方法，就能轻松破解各类问题。从简单的ax ≡ b(mod m)求解，到青蛙约会这类趣味应用题，同余方程的身影无处不在。本文将从同余方程的定义切入，详解其与不定方程的转化逻辑，依托扩展欧几里得算法搭建求解框架，结合例题，手把手教你从理论到实战的全流程，让你在同余问题中不再迷茫。下面就让我们正式开始吧！

一、同余方程的核心概念：从定义到转化

1.1 同余方程的定义

同余方程的标准形式为：ax ≡ b(mod m)，其中 a、b、m 是给定的整数，x 是待求的整数解。它的含义是：ax 除以 m 的余数与 b 除以 m 的余数相等，即ax - b能被 m 整除（记作m | (ax - b)）。

举个直观的例子：4x ≡ 2(mod 6)，这个方程的解是 x=2（4×2=8，8 mod 6=2）、x=5（4×5=20，20 mod 6=2）等，存在无数个整数解。

关键说明：

• 解的存在性：并非所有同余方程都有解。例如2x ≡ 1(mod 4)，无论 x 取何整数，2x 都是偶数，偶数 mod 4 的结果只能是 0 或 2，无法等于 1，因此无解；
• 解的形式：若方程有解，则解一定是周期性的，存在无数个整数解（后续将推导通解公式）；
• 核心目标：竞赛中通常要求求出最小正整数解，或判断方程是否无解。

1.2 同余方程与线性不定方程的转化

要解决同余方程，关键一步是将其转化为我们熟悉的 “二元一次不定方程”。根据同余方程的定义ax ≡ b(mod m)，可推导如下：

1. 由m | (ax - b)，可知存在整数 y，使得ax - b = my；
2. 移项后得到：ax - my = b；
3. 令y' = -y（y' 也是整数），方程进一步转化为：ax + my' = b。

此时，同余方程ax ≡ b(mod m)的求解问题，就等价于二元一次不定方程ax + my = b的整数解求解问题。而判断同余方程是否有解，也转化为判断不定方程是否有解 —— 这正是裴蜀定理的用武之地！

1.3 解的存在性判定：裴蜀定理的应用

根据裴蜀定理，二元一次不定方程ax + by = c有整数解的充要条件是gcd(a, b) | c（即 c 能被 a 和 b 的最大公约数整除）。

对应到同余方程转化后的不定方程ax + my = b，其有解的充要条件是gcd(a, m) | b。这也是判断同余方程ax ≡ b(mod m)是否有解的核心准则。

示例验证：

• 方程4x ≡ 2(mod 6)：a=4，m=6，b=2，gcd(4,6)=2，2 能整除 2，因此有解；
• 方程2x ≡ 1(mod 4)：a=2，m=4，b=1，gcd(2,4)=2，2 不能整除 1，因此无解；
• 方程3x ≡ 1(mod 10)：a=3，m=10，b=1，gcd(3,10)=1，1 能整除 1，因此有解。

二、核心求解工具：扩展欧几里得算法

当同余方程有解时，我们需要求出具体的解。此时，扩展欧几里得算法（exgcd）成为核心工具 —— 它不仅能计算 a 和 m 的最大公约数，还能同时求出不定方程ax + my = gcd(a, m)的一组特解，进而推导出同余方程的通解和最小正整数解。

2.1 扩展欧几里得算法的回顾

扩展欧几里得算法的核心逻辑基于欧几里得算法（辗转相除法）的递归过程，其核心思想是：在计算gcd(a, m)的同时，反向推导不定方程ax + my = gcd(a, m)的特解。

算法核心推导：

1. 递归终止条件：当 m=0 时，gcd(a, 0)=a，此时方程ax + 0*y = a的一组特解为x=1，y=0；
2. 递归过程：假设我们已经求出gcd(m, a mod m)的一组特解(x1, y1)，即m*x1 + (a mod m)*y1 = gcd(a, m)；
3. 由于a mod m = a - floor(a/m)*m（floor (a/m) 表示 a 除以 m 的商），代入上式得：m∗x1+(a−floor(a/m)∗m)∗y1=gcd(a,m)
4. 整理后：a∗y1+m∗(x1−floor(a/m)∗y1)=gcd(a,m)
5. 对比目标方程a*x + m*y = gcd(a, m)，可得当前层的特解：x=y1 y=x1−floor(a/m)∗y1

C++ 实现扩展欧几里得算法

#include <iostream>
using namespace std;

typedef long long LL;

// 扩展欧几里得算法：返回gcd(a,b)，并通过引用返回方程ax+by=gcd(a,b)的一组特解(x,y)
LL exgcd(LL a, LL b, LL& x, LL& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    LL x1, y1, d;
    d = exgcd(b, a % b, x1, y1);
    // 推导当前层特解
    x = y1;
    y = x1 - (a / b) * y1;
    return d;
}

int main() {
    LL a = 4, m = 6;
    LL x, y;
    LL d = exgcd(a, m, x, y);
    cout << "gcd(" << a << ", " << m << ") = " << d << endl;
    cout << "方程 " << a << "x + " << m << "y = " << d << " 的特解：x=" << x << ", y=" << y << endl;
    // 输出：gcd(4,6)=2；特解x= -1, y=1（4*(-1) +6*1=2）
    return 0;
}

2.2 同余方程的通解推导

当我们通过扩展欧几里得算法求出不定方程ax + my = gcd(a, m)的一组特解(x0, y0)后，需要进一步推导同余方程ax ≡ b(mod m)的通解。

步骤 1：求不定方程ax + my = b的特解

设d = gcd(a, m)，由于方程有解（d | b），令k = b / d。将特解(x0, y0)缩放 k 倍，得到ax + my = b的一组特解：x1=x0∗k y1=y0∗k

步骤 2：推导通解

不定方程ax + my = b的通解公式为：x=x1+k∗(m/d)(k∈Z) y=y1−k∗(a/d)(k∈Z)

其中，m/d是 x 的增量（周期），k 取任意整数时，x 和 y 都满足方程。

步骤 3：同余方程的最小正整数解

由于 x 的通解是周期性的，周期为m/d，因此同余方程ax ≡ b(mod m)的最小正整数解为： x min​=(x1 mod (m/d)+(m/d)) mod (m/d)

添加(m/d)再取模是为了避免 x1 为负数时出现负解。

示例推导：求4x ≡ 2(mod 6)的最小正整数解

1. 转化为不定方程：4x + 6y = 2；
2. 计算d = gcd(4,6)=2，k=2/2=1；
3. 求4x +6y=2的特解：通过 exgcd 求出4x +6y=2的特解x0=-1, y0=1，缩放 k=1 后，特解x1=-1；
4. 通解：x = -1 + k*(6/2) = -1 + 3k（k 为整数）；
5. 最小正整数解：( -1 mod 3 + 3 ) mod 3 = (2 + 3) mod 3=2，即 x=2（与之前的示例一致）。

三、实战例题 1：牛客网【模板】同余方程

题目链接：https://ac.nowcoder.com/acm/problem/229005

3.1 题目分析

题目描述：求关于 x 的同余方程ax ≡ 1(mod b)的最小正整数解，若无解输出 "-1"。

输入描述：第一行一个整数 T，表示 T 组数据；每组数据一行两个正整数 a、b（2≤a,b≤2×10⁹）。输出描述：每组数据输出最小正整数解或 "-1"。示例输入：23 102 4示例输出：7-1

核心思路：

• 方程转化为ax + by = 1（不定方程）；
• 有解的充要条件是gcd(a, b)=1（因为 b 是模数，1 必须被 gcd (a,b) 整除）；
• 用 exgcd 求出特解，再转化为最小正整数解。

3.2 C++ 实现

#include <iostream>
using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b, LL& x, LL& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    LL x1, y1, d;
    d = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return d;
}

LL solve(LL a, LL b) {
    LL x, y;
    LL d = exgcd(a, b, x, y);
    if (d != 1) {
        return -1; // 无解
    }
    // 转化为最小正整数解
    x = (x % b + b) % b;
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        LL a, b;
        cin >> a >> b;
        LL ans = solve(a, b);
        cout << ans << endl;
    }
    return 0;
}

3.3 代码验证

• 第一组输入：3 10 → 方程3x ≡1(mod10)；
  • gcd(3,10)=1，有解；
  • exgcd 求出特解x=7, y=-2（3×7 +10×(-2)=1）；
  • 最小正整数解为 7，输出 7；
• 第二组输入：2 4 → 方程2x ≡1(mod4)；
  • gcd(2,4)=2≠1，无解，输出 - 1。

3.4 关键优化

• 数据范围：a 和 b 可达 2×10⁹，必须使用 long long 避免溢出；
• 最小正整数解计算：(x % b + b) % b确保结果为正，即使 x 是负数；
• 效率：exgcd 的时间复杂度为 O (log min (a,b))，对于 2×10⁹的数据完全可以毫秒级完成。

四、实战例题 2：洛谷 P1516 青蛙的约会

题目链接：https://www.luogu.com.cn/problem/P1516

4.1 题目分析

题目描述：两只青蛙在纬度线上跳跃，青蛙 A 从坐标 x 出发，每次跳 m 米；青蛙 B 从坐标 y 出发，每次跳 n 米。纬度线总长 L 米（首尾相接），求它们跳多少次后碰面，若永远不能碰面输出 "Impossible"。

输入描述：一行五个整数 x、y、m、n、L。

输出描述：碰面次数或 "Impossible"。

示例输入：1 2 3 4 5 → 输出：4。

核心思路：

1. 设跳 t 次后碰面，此时青蛙 A 的坐标为x + mt，青蛙 B 的坐标为y + nt；
2. 碰面条件：(x + mt) - (y + nt) = kL（k 为整数，A 比 B 多跳 k 圈）；
3. 整理方程：(m - n)t - Lk = y - x；
4. 令a = m - n，b = L，c = y - x，方程转化为同余方程a*t ≡ c(mod b)；
5. 求解该同余方程，最小正整数解 t 即为答案。

4.2 C++ 实现

#include <iostream>
using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b, LL& x, LL& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    LL x1, y1, d;
    d = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return d;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    LL x, y, m, n, L;
    cin >> x >> y >> m >> n >> L;
    
    LL a = m - n;
    LL b = L;
    LL c = y - x;
    
    // 处理a为负数的情况，避免影响后续计算
    if (a < 0) {
        a = -a;
        c = -c;
    }
    
    LL x0, y0, d;
    d = exgcd(a, b, x0, y0);
    
    if (c % d != 0) {
        cout << "Impossible" << endl;
    } else {
        // 求特解
        x0 = x0 * (c / d);
        // 通解：t = x0 + k*(b/d)，求最小正整数解
        LL k1 = b / d;
        x0 = (x0 % k1 + k1) % k1;
        cout << x0 << endl;
    }
    
    return 0;
}

4.3 代码验证

示例输入：1 2 3 4 5 → x=1，y=2，m=3，n=4，L=5；

• a = 3-4 = -1 → 处理后 a=1；
• c = 2-1 = 1 → 处理后 c=-1；
• 方程转化为1*t ≡ -1(mod 5) → 等价于t ≡4(mod5)；
• exgcd 求出1*t +5*y = -1的特解x0=-1；
• 最小正整数解：(-1 mod5 +5) mod5=4，输出 4（跳 4 次后碰面）。

4.4 细节处理

• a 为负数：当 m < n 时，a = m-n 为负数，此时将 a 和 c 同时取反，方程等价不变；
• 最小正整数解：通过(x0 % k1 + k1) % k1确保结果为正；
• 无解判断：当 c 不能被 d 整除时，输出 "Impossible"。

五、常见误区与避坑指南

5.1 方程转化错误

• 误区：将同余方程ax ≡ b(mod m)错误转化为ax - my = -b或其他形式，导致后续求解错误；
• 避坑：严格按照定义推导，确保转化后的不定方程为ax + my = b（或等价形式），避免符号错误。

5.2 忽略解的存在性判定

• 误区：未判断gcd(a,m) | b就直接求解，导致无效计算；
• 避坑：先计算d = gcd(a,m)，若b % d != 0，直接输出无解，无需后续步骤。

5.3 最小正整数解计算错误

• 误区：直接对特解 x1 取模，未处理负数情况（如 x1=-1，m/d=3，直接取模得 - 1，而非 2）；
• 避坑：使用公式(x1 % (m/d) + (m/d)) % (m/d)，确保结果为正整数。

5.4 数据溢出问题

• 误区：使用 int 类型存储 a、m、b 等变量，当数据达到 1e9 时发生溢出；
• 避坑：所有变量统一使用 long long 类型，尤其是在计算a*x、m*y等乘积时。

5.5 混淆通解的周期

• 误区：将通解中 x 的周期误认为 m，而非m/d；
• 避坑：牢记通解周期为m/d（d=gcd (a,m)），例如4x ≡2(mod6)中，d=2，周期为 6/2=3，与示例中 x=2、5、8... 一致。

总结

同余方程是数论中的核心考点，其求解的核心逻辑是 “转化为不定方程 + 扩展欧几里得算法求解”。如果在学习过程中遇到具体题目无法解决，或想了解中国剩余定理、快速乘等延伸知识点，可以随时留言交流。后续将持续更新数论进阶内容，敬请关注！