小指针

V1

2022/03/26阅读:86主题:凝夜紫

中国剩余定理及其扩展

封面原图
封面原图

阅读本文所需前置知识:欧几里得算法及其扩展乘法逆元

中国剩余定理

中国古代的数学巨著《孙子算经》中提到一个“物不知数”问题,原文如下:”有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?“。

用现代语言解释,既,一个整数除以三余二,除以五余三,除以七余二,求这个整数。《孙子算经》中首次提到了同余方程组问题,以及以上具体问题的解法,因此在中文数学文献中也会将中国剩余定理称为孙子定理。

现代数论中,中国剩余定理,是一个关于一元线性同余方程组的定理,说明了一元线性同余方程组有解的准则以及求解方法。

前置知识:一元线性同余方程

在数论中,线性同余方程是最基本的同余方程,“线性”表示方程只有一个未知数,即形如: 的方程。

如何求出未知数x呢?

  1. 根据同余的含义: ,那么一定有整数y使得
  2. 把my移动到右面,得到:
  3. 如果我们假设 ,那么步骤二的方程可以写为:
  4. 根据裴蜀定理,上面的方程有解的前提是 gcd(a,m)|b,其中|表示整除。
  5. 用扩展欧几里德算法求出一组整数 ,使得
  6. 现在有两组等式:1. ;2. 。其中b又一定是gcd(a,m)的倍数,那么我们只要将等式2两面同时扩大b/gcd(a,m)倍不就能得到等式1了嘛。
  7. 扩大后就得到了
  8. 此时 的系数是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时,对于求解公式 中的每一项除了 之外,全部是 。所以有 ,那么当i取其他值时候同理。这样我们就证明了最终的线性同余方程组的求解公式,也就是中国剩余定理。

举个例子

(公式推导实在太抽象了。不如使用实际的例子推一遍来的清晰。)
以《孙子算经》里面的“物不知数”问题为例,其中的线性同余方程组是:

  1. 首先把例子给的值对应到模型上,其中
  2. 首先算出M, ,再依次求出 , 算出 的逆元 ,其中因为m可能是非质数,所以这里求逆元要用扩展欧几里得算法,求出
  3. 代入到求解公式:
  4. 233只是原线性同余方程组的一个解,那么他的通解为:
  5. 通过通解,我们还可以进一步求出最小的非负整数解,即当k=-2时,x=23

扩展中国剩余定理的推导

注意在标准的中国剩余定理上,有一个重要的前提:所有的m均满足两两互质

扩展中国剩余定理可以在不满足这个重要条件下,仍然求出最小的非负整数x

公式推导

  1. 先只看前两个方程:

  2. 把模数运算转换为四则运算:

  3. 联立两个公式,得到:

  4. 移项,得到:

  5. 也就是: 。如此,我们就把公式转换成了扩展欧几里德算法的样式。

  6. 如标准中国剩余定理中的推导一样,使用扩展欧几里德找出一组解 ,使得

  7. 此时的无解条件,就是 无法整除 。(参考前置知识线性同余方程的无解条件)

  8. 假设, ,此时,显然只要把 同时扩大y倍,就能得到

  9. 根据线性同余方程的通解,我们知道一个重要的性质,即:


    k为任意整数时,新的 仍然满足公式

    此处的证明:

    1. 将新的 带入到公式中,得到:
    2. 将括号展开:
    3. 消去同加同减,得到:
    4. 该公式本质与原公式是一样的,因此步骤9的性质成立。
  10. 把上面得到的新 带入到原始方程组:

  11. 上面公式的前半部分 ,全部是已知的,也就是这部分可以看成一个新的整数,我们记作 ;后面部分的 则是 的最小公倍数,也是一个确定的数,我们记作

    那么,上述公式可以写成:

  12. 所以我们得到了前两个方程的通解:

  13. 可以看到该通解与原方程组中的方程非常相似。因此,我们使用这种方式两两合并,最后就可以合并出整个方程组的通解。

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;
}

分类:

数学

标签:

数学编程

作者介绍

小指针
V1