这篇文章上次修改于 316 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

ACM程序课算法笔记18——中国剩余定理

问题引入

《孙子算经》中有问「物不知数」：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

即希望x同时满足多个模线性方程，然后求解。比如：

x≡2(mod 3)

x≡3(mod 5)

x≡2(mod 7)

同时明朝数学家程大位在《算法统宗》中给出：

三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五便得知。

2 x 70 + 3 x 21 + 2 x 15 = 233 ；233 % 105 = 23

中国剩余定理

中国剩余定理可求解如下形式的一元线性同余方程组

x≡a1(mod m1)

x≡a2(mod m2)

…

x≡an(mod mn)

前提

若m,m2,m3,是两两互质的正整数

结论

先得到N = ∏m = m1m2m3…mn
得到Mi = N / mi
xi 就是线性同余方程 Mixi ≡ 1 (mod mn)的一个解，也就是Mi的逆元
x = a1M1x1+a2M2x2+…+anMnxn

分析

限制条件的分析，为什么一定要互质？

在求xi的时候，我们得到的同余方程是Mixi ≡ 1 (mod mn)，要使它有解，也就是mn和Mi需要互质，它俩的gcd = 1

答案的正确性分析

对于Mi是所有的m的乘积，除了mi，所以在计算除了第i条同余方程的时候，Mi都会被其他的m直接除掉，因为是它们的倍数。所以在考虑第i条式子的时候，实际上就是 ai Mi xi ≡ ai (mod mi)也就是

Mi xi ≡ 1(mod mi)，又因为xi和Mi是逆元，所以成立，答案合理。

using i64 = long long;
i64 extendGcd(i64 a, i64 b, i64 &x, i64 &y){
    if (b == 0){
        x = 1;
        y = 0;
        return a;
    }
    i64 d = extendGcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

long long CRT(int k, const vector<int>& arrA, const vector<int>& arrMod) {
  long long N = 1, ans = 0;
  for (int i = 1; i <= k; i++) N *= arrMod[i];
  for (int i = 1; i <= k; i++) {
    long long M = N / arrMod[i], x, y;
    extendGcd(M , arrMod[i], x, y);  // xi * M ≡ 1 (mod mi)
    ans = (ans + arrA[i] * M * x % N) % N;
  }
  return (ans % N + N) % N;
}

局限性

也就是算法成立的前提，所有m之间要互质。

另一个角度看算法

这是个人想法，算法本质上就是不断地让x适配某个同余方程，对x缝缝补补，比如我先让x适配第一个方程，再让x适配第二个方程，重点在于，适配方程的同时，我不能去导致其他同余方程的值变化。

同余方程的特点是，只要我在x上加了m的倍数，改成立条件就不变。所以我每次为了适配方程i成立，我不能去修改其他同余方程的余数。有点像拼魔方，我一点点往后拼，都不破坏之前已经拼好的面。

在适配的时候，我只要每次适配增加的值都是其他m的倍数，那么其他条件式的余数就都不会变了。然后根据这个增加值，直到这个式子成立。

如果能理解这个原理，那么求一般情况也会更加简单

中国剩余定理一般情况

一般情况就指的是模数可能不互质。

但是有我们的另一个角度去思考算法，实际上问题也可以从这个角度出发。

对于n条同余式子，如果不互质，就有可能出现无解的情况。

同样使用适配的思路，先满足第一个式子，此时再去满足第二个式子的时候，只要让答案加上第一个式子模数的倍数即可。

那么第三个式子也就是增加前面两个的模数的倍数。

以此类推每次的添加，实际上就是前面的模数的lcm。

result + k lcm ≡ ai (mod mi)

k lcm ≡ (ai - result) % mi (mod mi)

求得k后

result += k lcm

即可。

Mai Icy