小指针
2022/03/26阅读:86主题:凝夜紫
中国剩余定理及其扩展

阅读本文所需前置知识:欧几里得算法及其扩展,乘法逆元
中国剩余定理
中国古代的数学巨著《孙子算经》中提到一个“物不知数”问题,原文如下:”有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?“。
用现代语言解释,既,一个整数除以三余二,除以五余三,除以七余二,求这个整数。《孙子算经》中首次提到了同余方程组问题,以及以上具体问题的解法,因此在中文数学文献中也会将中国剩余定理称为孙子定理。
现代数论中,中国剩余定理,是一个关于一元线性同余方程组的定理,说明了一元线性同余方程组有解的准则以及求解方法。
前置知识:一元线性同余方程
在数论中,线性同余方程是最基本的同余方程,“线性”表示方程只有一个未知数,即形如: 的方程。
如何求出未知数x呢?
-
根据同余的含义: ,那么一定有整数 y
使得 。 -
把my移动到右面,得到: 。 -
如果我们假设 ,那么步骤二的方程可以写为: 。 -
根据裴蜀定理,上面的方程有解的前提是 gcd(a,m)|b
,其中|
表示整除。 -
用扩展欧几里德算法求出一组整数 ,使得 。 -
现在有两组等式:1. ;2. 。其中 b
又一定是gcd(a,m)
的倍数,那么我们只要将等式2
两面同时扩大b/gcd(a,m)
倍不就能得到等式1
了嘛。 -
扩大后就得到了 。 -
此时 的系数是1,那么我们只要把这个系数扩展到全部整数,就得到了x的通解: ,其中 d=gcd(a,m)
。
Code
输入格式
第一行包含整数 n。 接下来 n 行,每行包含一组数据 a,b,m。
输入样例
2
2 3 6
4 3 5
输出样例
impossible
-3
#include <iostream>
using namespace std;
typedef long long LL;
int exgcd(int a, int m, int &x, int &y) {
if (!m) {
x = 1, y = 0;
return a;
}
int d = exgcd(m, a % m, y, x);
y -= a / m * x;
return d;
}
int main() {
int n;
cin >> n;
while (n -- ) {
int a, b, m, x, y;
cin >> a >> b >> m;
int d = exgcd(a, m, x, y);
if (b % d) puts("impossible");
// 最后结果对m取模是为了让答案保持在m之内。
else cout << (LL)x * b / d % m << endl;
}
return 0;
}
标准中国剩余定理的推导
在上面,我们知道了单个线性同余方程的求解方法,那么如果线性同余方程扩展为线性同余方程组呢?
对于问题 ,若其中 满足两两互质,则可以使用标准的中国剩余定理求解,形如:
「求解公式」
其中
, (也就是除了 以外的 个数的乘积) , 为 的逆元。即, 。
公式证明
在上面公式的基础上左右两面同时乘以
又因为当
所以当i=1
时,对于求解公式
举个例子
(公式推导实在太抽象了。不如使用实际的例子推一遍来的清晰。)
以《孙子算经》里面的“物不知数”问题为例,其中的线性同余方程组是:
-
首先把例子给的值对应到模型上,其中 -
首先算出M, -
代入到求解公式: -
而 233
只是原线性同余方程组的一个解,那么他的通解为: -
通过通解,我们还可以进一步求出最小的非负整数解,即当 k=-2
时,x=23
。
扩展中国剩余定理的推导
注意在标准的中国剩余定理上,有一个重要的前提:「所有的m均满足两两互质」。
扩展中国剩余定理可以在不满足这个重要条件下,仍然求出最小的非负整数x
。
公式推导
-
先只看前两个方程:
-
把模数运算转换为四则运算:
-
联立两个公式,得到:
-
移项,得到:
-
也就是:
-
如标准中国剩余定理中的推导一样,使用扩展欧几里德找出一组解
-
此时的无解条件,就是
-
假设,
-
根据线性同余方程的通解,我们知道一个重要的性质,即:
当k
为任意整数时,新的此处的证明:
-
将新的 -
将括号展开: -
消去同加同减,得到: -
该公式本质与原公式是一样的,因此步骤9的性质成立。
-
-
把上面得到的新
-
上面公式的前半部分
那么,上述公式可以写成:
-
所以我们得到了前两个方程的通解:
-
可以看到该通解与原方程组中的方程非常相似。因此,我们使用这种方式两两合并,最后就可以合并出整个方程组的通解。
Code
输入格式
第 1 行包含整数 n。
第 2…n+1 行:每 i+1 行包含两个整数 ai 和 mi,数之间用空格隔开。
输出格式
输出最小非负整数 x,如果 x 不存在,则输出 −1。
如果存在 x,则数据保证 x 一定在 64 位整数范围内。
输入样例
2 8 7 11 9
输出样例
31
#include <iostream>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main() {
int n;
cin >> n;
LL m1, a1;
cin >> m1 >> a1;
bool has_answer = true;
for (int i = 0; i < n - 1; i ++ ) {
LL m2, a2;
cin >> m2 >> a2;
LL k1, k2;
LL d = exgcd(m1, m2, k1, k2); // 步骤6
// 步骤7, 无解判断
if ((a2 - a1) % d) {
has_answer = false;
break;
}
k1 *= (a2 - a1) / d; // 步骤9,得到新的k1
LL t = m2 / d;
// k1 % t 让新k1变成最小,如此做是为了变成非负的。
k1 = (k1 % t + t) % t;
a1 = m1 * k1 + a1; // 步骤11,得到新的a1
m1 = abs(m1 / d * m2); // 步骤11,得到新的m1
}
if (has_answer) {
// 最后方程组变成一个方程 计算x的值
cout << (a1 % m1 + m1) % m1 << endl;
}
else puts("-1");
return 0;
}
分类:
数学标签:
数学编程作者介绍