中国剩余定理

标签：剩余 公倍数 定理 除以 int 中国 余数 LL

中国剩余定理

先看一道\(poj\)上的题目：【\(POJ1006\)】 \(Biorhythms\)

题意：
　　人自出生起就有体力，情感和智力三个生理周期，分别为\(23\)，\(28\)和\(33\)天。一个周期内有一天为峰值，在这一天，人在对应的方面（体力，情感或智力）表现最好。通常这三个周期的峰值不会是同一天。现在给出三个日期，分别对应于体力，情感，智力出现峰值的日期。然后再给出一个起始日期，要求从这一天开始，算出最少再过多少天后三个峰值同时出现。

分析：
　　首先我们要知道，任意两个峰值之间一定相距整数倍的周期。假设一年的第\(N\)天达到峰值，则 下次 达到峰值的时间为\(N+Tk\)
(\(T\)是周期，\(k\)是任意正整数)。所以，三个峰值同时出现的那一天(\(S\))应满足
\(S=N_1+T_1∗k_1=N_2+T_2∗k_2=N_3+T_3∗k_3\)
\(N_1,N_2,N_3\)分别为为体力，情感，智力出现峰值的日期， \(T_1，T_2,T_3\) 分别为体力，情感，智力周期。 我们需要求出\(k_1,k_2,k_3\)三个非负整数使上面的等式成立。

想直接求出\(k_1,k_2,k_3\)貌似很难，但是我们的目的是求出\(S\)， 可以考虑从结果逆推。根据上面的等式，\(S\) 满足三个要求：

• 除以\(T_1\)余数为\(N_1\)
• 除以\(T_2\)余数为\(N_2\)
• 除以\(T_3\)余数为\(N_3\)

这样我们就把问题转化为求一个 最小数，该数

• 除以\(T_1\)余\(N_1\)
• 除以\(T_2\)余\(N_2\)
• 除以\(T_3\)余\(N_3\)

这就是著名的中国剩余定理，我们的老祖宗在几千年前已经对这个问题想出了一个精妙的解法。依据此解法的算法，时间复杂度可达到\(O(1)\)

中国剩余定理

在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以\(3\)余\(2\)），五五数之剩三（除以\(5\)余\(3\)），七七数之剩二（除以\(7\)余\(2\)），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。具体解法分三步：

• 找出三个数：

  • 从\(3\)和\(5\)的公倍数中找出被\(7\)除余\(1\)的最小数\(15\)
  • 从\(3\)和\(7\)的公倍数中找出被\(5\)除余\(1\) 的最小数\(21\)
  • 从\(5\)和\(7\)的公倍数中找出除\(3\)余\(1\)的最小数\(70\)

• 用\(15\)乘以\(2\)（\(2\)为最终结果除以\(7\)的余数），用\(21\)乘以\(3\)（\(3\)为最终结果除以\(5\)的余数），同理，用\(70\)乘以\(2\)（\(2\)为最终结果除以\(3\)的余数），然后把三个乘积相加\(15∗2+21∗3+70∗2\),得到和\(233\)。

• 用\(233\)除以\(3，5，7\)三个数的最小公倍数\(105\)，得到余数\(23\)，即\(233\%105=23\)
  。这个余数\(23\)就是符合条件的最小数。

就这么简单。我们在感叹神奇的同时不禁想知道古人是如何想到这个方法的，有什么基本的数学依据吗？

　　我们将“孙子问题”拆分成几个简单的小问题，从零开始，试图揣测古人是如何推导出这个解法的。

首先，我们假设:

• \(n_1\)是满足除以\(3\)余\(2\)的一个数，比如\(2，5，8\)等等，也就是满足\(3∗k+2（k>=0）\) 的一个任意数。
• \(n_2\)是满足除以\(5\)余\(3\)的一个数
• \(n_3\)是满足除以\(7\)余\(2\)的一个数

有了前面的假设，我们先从\(n_1\)这个角度出发，已知\(n_1\)满足除以\(3\)余\(2\)，能不能使得\(n_1+n_2\)的和仍然满足除以\(3\)余\(2\)？进而使得\(n_1+n_2+n_3\)的和仍然满足除以\(3\)余\(2\)？

　这就牵涉到一个 最基本数学定理，如果有\(a\%b=c\)，则有\((a+k∗b)\%b=c\)(\(k\)为非零整数)，换句话说，如果一个除法运算的余数为\(c\)
，那么被除数与\(k\)倍的除数相加（或相减）的和（差）再与除数相除，余数不变。

以此定理为依据，如果\(n_2\)是\(3\)的倍数，\(n_1+n_2\)就依然满足除以\(3\)余\(2\)。同理，如果\(n_3\)也是\(3\)的倍数，那么\(n_1+n_2+n_3\)
的和就满足除以\(3\)余\(2\)。这是从\(n_1\)的角度考虑的，再从\(n_2\)，\(n_3\)的角度出发，我们可推导出以下三点：

• 为使\(n_1+n_2+n_3\)的和满足除以\(3\)余\(2\)，\(n_2\)和\(n_3\)必须是\(3\)的倍数

• 为使\(n_1+n_2+n_3\)的和满足除以\(5\)余\(3\)，\(n_1\)和\(n_3\)必须是\(5\)的倍数

• 为使\(n_1+n_2+n_3\)的和满足除以\(7\)余\(2\)，\(n_1\)和\(n_2\)必须是\(7\)的倍数

因此，为使\(n_1+n_2+n_3\)的和作为“孙子问题”的一个最终解，需满足：

• \(n_1\)除以\(3\)余\(2\)，且是\(5\)和\(7\)的公倍数。
• \(n_2\)除以\(5\)余\(3\)，且是\(3\)和\(7\)的公倍数。
• \(n_3\)除以\(7\)余\(2\)，且是\(3\)和\(5\)的公倍数。

所以，孙子问题解法的本质是:

• 从\(5\)和\(7\)的公倍数中找一个除以\(3\)余\(2\)的数\(n_1\)
• 从\(3\)和\(7\)的公倍数中找一个除以\(5\)余\(3\)的数\(n_2\)
• 从\(3\)和\(5\)的公倍数中找一个除以\(7\)余\(2\)的数\(n_3\)

再将三个数相加得到解。在求\(n_1，n_2，n_3\)
时又用了一个小技巧，以\(n_1\)为例，并非从\(5\)和\(7\)的公倍数中直接找一个除以\(3\)余\(2\)的数，而是 先找一个 除以\(3\)余\(1\)的数，再乘以\(2\)。也就是先求出\(5\)和\(7\)的公倍数模\(3\)下的 逆元 ，再用逆元去乘余数。

这里又有一个数学公式，如果\(a\%b=c\)，那么\((a∗k)\%b=a\%b+a\%b+…+a\%b=c+c+…+c=k∗c(k>0)\),也就是说，如果一个除法的余数为\(c\)，那么被除数的\(k\)倍与除数相除的余数为\(k∗c\)。展开式中已证明。

最后，我们还要清楚一点，\(n_1+n_2+n_3\)
只是问题的一个解，并不是最小的解。如何得到最小解？我们只需要从中最大限度的减掉\(3，5，7\)的公倍数\(105\)即可。道理就是前面讲过的定理 如果\(a\%b=c\)，则有\((a−k∗b)\%b=c\)
所以\((n_1+n_2+n_3)\%105\)就是最终的最小解。

这样一来就得到了中国剩余定理的公式：

【中国剩余定理公式】

设\(x \in Z\),有

\[\large \left\{\begin{matrix} x \equiv a_1(mod \ m_1) & \\ x \equiv a_2(mod \ m_2) & \\ x \equiv a_3(mod \ m_3) & \\ ... & \\ x \equiv a_n(mod \ m_n) & \end{matrix}\right. \]

令$$
\large \left{\begin{matrix}
M=m_1m_2m_3...m_n & \
M_i=M/m_i& \
t_i 是M_i关于m_i 的逆元，即M_it_i \equiv 1 (mod \ m_i)
\end{matrix}\right.

\[ 则 $$x=\sum_{i=1}^{n}a_iM_it_i\]

【代码实现】

模数互质：

P3868 [TJOI2009] 猜数字

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 20;
int n;
LL a[N], m[N];
LL ans, x, y;

// P3868 [TJOI2009] 猜数字
/**
 由 bi | (n-ai), 也就是 n % b[i] =a[i]
 标准的中国剩余定理
 */

//快速乘
LL ksc(LL a, LL b, LL mod) {
    LL res = 0;
    while (b) {
        if (b & 1) res = (res + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}

//扩展欧几里得
LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main() {
    cin >> n;

    // a[i]：余数,b[i]:分组个数
    for (int i = 1; i <= n; i++) cin >> a[i];

    LL M = 1;
    for (int i = 1; i <= n; i++) cin >> m[i], M *= m[i]; // M是累乘积

    // a[i]可能为负数，预处理成正数
    for (int i = 1; i <= n; i++) a[i] = (a[i] % m[i] + m[i]) % m[i];

    // 中国剩余定理
    for (int i = 1; i <= n; i++) {
        exgcd(M / m[i], m[i], x, y);                  // 求逆元
        x = (x % m[i] + m[i]) % m[i];                 // 防负数
        ans = (ans + ksc(a[i], M / m[i] * x, M)) % M; // 快速乘
    }

    printf("%lld\n", ans);
    return 0;
}

P1495 【模板】中国剩余定理(CRT)/曹冲养猪

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 10;
int a[N], m[N];
int n;

void exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b)
        x = 1, y = 0;
    else {
        exgcd(b, a % b, y, x);
        y -= a / b * x;
    }
}

int main() {
    cin >> n;
    LL M = 1;

    // a[i]：余数,m[i]:分组个数
    // 注意录入顺序，与P3868进行对比
    for (int i = 1; i <= n; i++) {
        cin >> m[i] >> a[i];
        M *= m[i];
    }

    LL res = 0, x, y;
    for (int i = 1; i <= n; i++) {
        exgcd(M / m[i], m[i], x, y);
        res += a[i] * M / m[i] * x;
    }

    printf("%lld\n", (res % M + M) % M);
    return 0;
}

中国剩余定理扩展——求解模数不互质情况下的线性方程组：

大神博客

推荐题目

模数不互质模板：洛谷P4777 【模板】扩展中国剩余定理（EXCRT）.

标签：剩余,公倍数,定理,除以,int,中国,余数,LL
From： https://www.cnblogs.com/littlehb/p/17073570.html