线性同余方程
定义
形如
的方程称为 线性同余方程（Linear Congruence Equation）。其中，、 和 为给定整数， 为未知数。需要从区间 中求解 ，当解不唯一时需要求出全体解。
用逆元求解
首先考虑简单的情况，当 和 互素（coprime 或 relatively prime）时，即 。
此时可以计算 的逆元，并将方程的两边乘以 的逆元，可以得到唯一解。
证明
接下来考虑 和 不互素（not coprime），即 的情况。此时不一定有解。例如， 没有解。
设 ，即 和 的最大公约数，其中 和 在本例中大于 1。
当 不能被 整除时无解。此时，对于任意的 ，方程 的左侧始终可被 整除，而右侧不可被 整除，因此无解。
如果 整除 ，则通过将方程两边 、 和 除以 ，得到一个新的方程：
其中 和 已经互素，这种情形已经解决，于是得到 作为 的解。
很明显， 也将是原始方程的解。这不是唯一的解。可以看出，原始方程有如下 个解：
总之，线性同余方程的 解的数量 等于 或等于 。
用扩展欧几里得算法求解
根据以下两个定理，可以求出线性同余方程 的解。
定理 1：线性同余方程 可以改写为如下线性不定方程：
其中 和 是未知数。这两个方程是等价的，有整数解的充要条件为 。
应用扩展欧几里德算法可以求解该线性不定方程。根据定理 1，对于线性不定方程 ，可以先用扩展欧几里得算法求出一组 ，也就是 ，然后两边同时除以 ，再乘 。就得到了方程
于是找到方程的一个解。
定理 2：若 ，且 、 为方程 的一组解，则该方程的任意解可表示为：
并且对任意整数 都成立。
根据定理 2，可以从已求出的一个解，求出方程的所有解。实际问题中，往往要求出一个最小整数解，也就是一个特解
其中有
如果仔细考虑，用扩展欧几里得算法求解与用逆元求解，两种方法是等价的。
实现
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | int ex_gcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int d = ex_gcd(b, a % b, x, y);
int temp = x;
x = y;
y = temp - a / b * y;
return d;
}
bool liEu(int a, int b, int c, int& x, int& y) {
int d = ex_gcd(a, b, x, y);
if (c % d != 0) return false;
int k = c / d;
x *= k;
y *= k;
return true;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | def ex_gcd(a, b, x, y):
if b == 0:
x = 1
y = 0
return a
d = ex_gcd(b, a % b, x, y)
temp = x
x = y
y = temp - a // b * y
return d
def liEu(a, b, c, x, y):
d = ex_gcd(a, b, x, y)
if c % d != 0:
return 0
k = c // d
x = x * k
y = y * k
return 1
|
本页面主要译自博文 Модульное линейное уравнение первого порядка 与其英文翻译版 Linear Congruence Equation。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。
习题
「NOIP2012」同余方程
本页面最近更新：2024/10/9 22:38:42，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：iamtwz, aofall, CoelacanthusHex, Enter-tainer, Great-designer, Haohu Shen, Ir1d, ksyx, kZime, leoleoasd, Marcythm, MegaOwIer, Menci, ouuan, Persdre, Phemon, shawlleyw, shuzhouliu, sshwy, stevebraveman, Tiphereth-A, tsentau, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用