数学之扩展欧几里得算法-线性同余方程

问题描述

给定三个整数 a,b,m，你需要求解一个 最小非负整数 x ，使其满足 a×x≡b(mod m)，如果无解则输出 -1。

输入格式

输入 t 组数据，每组数据包含以下内容：

输入一行，包含三个整数 a,b,m。

输出格式

对于每组数据输出一行，如果存在符合题目要求的最小非负整数解 x，直接输出；如果不存在该解，则输出 -1。

样例输入

7
2 3 6
-12 21 12
4 9 8
2 3 9 
1 2 3
8 9 1
-1 -1 3

样例输出

-1
-1
-1
6
2
0
1

评测数据规模

同时数据保证 a,b不为 0。

---

问题分析

我们需要求解方程 a×x≡b (mod m)，即找到一个整数 x，使得 a×x 除以 m 的余数是 b。这个问题可以转化为一个不定方程的形式，从而更容易理解和求解。

---

转化为不定方程

---

不定方程的解

不定方程 a×x+m×y=b 是否有解，取决于 b 是否能被 gcd⁡(a,m) 整除：

1. 有解条件：如果 gcd⁡(a,m)整除 b，则方程有解。

2. 无解条件：如果 gcd⁡(a,m) 不能整除 b，则方程无解。

如果方程有解，我们可以通过扩展欧几里得算法求解。

---

扩展欧几里得算法的作用

扩展欧几里得算法用于求解方程：

它不仅能求出 gcd⁡(a,m)，还能求出满足上述方程的整数解 x 和 y。

对于我们的方程 a×x+m×y=b，如果 gcd⁡(a,m) 整除 b，我们可以将扩展欧几里得算法求得的解 x 和 y 进行调整，得到方程的特解。

---

调整解的过程

1. 特解调整：

   • 扩展欧几里得算法求解的是 a×x+m×y=gcd⁡(a,m)。

   • 我们需要将解 x 和 y 乘以 b/gcd⁡(a,m)，得到方程 a×x+m×y=b 的特解。

2. 最小非负解调整：

   • 方程的解在模 m/gcd⁡(a,m) 意义下是唯一的。

   • 通过取模运算，将解 x 调整为最小的非负整数解。

---

为什么这样设计解决方案？

1. 转化为不定方程：

   • 将模运算转化为不定方程，便于利用数论中的工具（如扩展欧几里得算法）求解。

   • 不定方程的形式更直观，易于理解。

2. 扩展欧几里得算法：

   • 扩展欧几里得算法是求解线性不定方程的标准工具。

   • 它不仅能求出最大公约数，还能求出方程的解。

3. 调整解：

   • 通过调整解，确保得到的最小非负整数解满足原方程。

   • 这是为了满足题目对解的要求（最小非负整数）。

---

示例

解题代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;// 扩展欧几里得算法，求解 ax + by = gcd(a, b) 的解 x 和 y
ll exgcd(ll a, ll b, ll &x, ll &y) {if (b == 0) {x = 1, y = 0; // 当 b = 0 时，gcd(a, b) = a，此时 x = 1, y = 0return a;}// 递归求解 gcd(b, a % b)，并更新 x 和 yll d = exgcd(b, a % b, y, x);y -= a / b * x; // 根据递归结果调整 y 的值return d; // 返回 gcd(a, b)
}// 获取绝对值
ll getabs(ll x) { return x < 0 ? -x : x; }int main() {int t;cin >> t; // 读取测试用例数量while (t--) {ll a, b, m;cin >> a >> b >> m; // 读取 a, b, mll x, y;// 使用扩展欧几里得算法求解 gcd(|a|, |m|) 以及对应的 x 和 yll d = exgcd(getabs(a), getabs(m), x, y);// 如果 b 不能被 gcd(a, m) 整除，则方程无解if (b % d) {cout << -1 << '\n';} else {// 调整 x 的值，使其成为方程 a * x ≡ b (mod m) 的特解x *= (a < 0 ? -1 : 1) * (b / d);// 将 x 调整为最小的非负整数解x = (x % (m / d) + (m / d)) % (m / d);// 输出结果cout << x << '\n';}}return 0;
}

关键步骤解释

1. x *= (a < 0 ? -1 : 1) * (b / d);

• 作用：调整 x 的值，使其成为方程 a×x≡b (mod m)的特解。

• 解释：

  • 扩展欧几里得算法求解的是 ∣a∣×x+∣m∣×y=gcd⁡(∣a∣,∣m∣) 的解。

  • 由于我们需要的是 a×x≡b (mod m)的解，因此需要根据 a 的符号调整 x 的符号。

  • 同时，方程的解需要乘以 b/d，因为扩展欧几里得算法求解的是 gcd⁡(∣a∣,∣m∣)，而我们需要的是 b。

  • 因此，x *= (a < 0 ? -1 : 1) * (b / d); 将 x 调整为方程的特解。

2. x = (x % (m / d) + (m / d)) % (m / d);

• 作用：将 x 调整为最小的非负整数解。

• 解释：

  • 方程 a×x≡b (mod m)的解在模 m/d意义下是唯一的。

  • 通过 x % (m / d)，我们将 x 限制在 [0,m/d−1]的范围内。

  • 由于取模运算的结果可能是负数，我们加上 m/d 确保结果非负。

  • 最后再次取模 m/d，确保结果在 [0,m/d−1] 范围内。

  • 这样得到的 x 就是方程的最小非负整数解。