算法——中国剩余定理（孙子定理）

阳光穿透心脏的1/2处 2022-06-03 07:29 269阅读 0赞

借15级上机的一道题[数论の重逢][Link 1]来总结一下中国剩余定理

先举一个小例子

> 问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

说明白一点就是说，存在一个数x，除以3余2，除以5余三，除以7余二，然后求这个数。上面给出了解法。再明白这个解法的原理之前，需要先知道一下两个定理。

> 定理1：几个数相加，如果存在一个加数，不能被数a整除，那么它们的和，就不能被整数a整除。
> 
> 定理2：两数不能整除，若除数扩大（或缩小）了几倍，而被除数不变，则其商和余数也同时扩大（或缩小）相同的倍数（余数必小于除数）。

现给出求解该问题的具体步骤：

*  求出最小公倍数(这里讨论的都是两两互质的情况)
    
    lcm=3\*5\*7=105
 *  求各个数所对应的基础数
    
    观察求每个数对应的基础数时候的步骤，比如第一个。105÷3=35。显然这个35是除了当前这个数不能整除以外都能够被其他数整除，就是其他数的最小公倍数。相当于找到了最小的开始值，用它去除以3发现正好余2。那么这个基础数就是35。
    
    > 105÷3=35
    > 
    > 35÷3=11……2 //基础数35
    
    记住35的特征，可以整除其他数但是不能被3整除，并且余数是2。体现的还不够明显，再看下5对应的基础数。21是其他数的最小公倍数，但是不能被5整除，用21除以5得到的余数是1，而要求的数除以5应该是余1的。所以余数被扩大，就得到了相应的基础数63。
    
    > 105÷5=21
    > 
    > 21÷5=4……1
    > 
    > 定理2把1扩大3倍得到3，那么被除数也扩大3倍，得到21\*3=63//基础数63
    
    记住这个数的特征，可以被其他数整除但是被5除应该余三。同理，我们得到了第三个基础数30，那么他的特征就是：可以被其他数整除，但是不能被7整除，并且余数为2。
    
    > 105÷7=15
    > 
    > 15÷7=2……1
    > 
    > 定理2把1扩大2倍得到2，那么被除数也扩大2倍，得到15\*2=30//基础数30
 *  基础数加和（注意：基础数不一定就是正数）
    
    > 35+63+30=128
    
    对于3来说，可以把63+30的和看作一个整体，应该他们都可以被3整除。看着上面写出的三个数的特征，运用定理1来说，就是在35的基础上加上一个可以被3整除的倍数，那么得到的结果依然还是满足原先的性质的，就是128除以同样还是余2的。同理，对于5还说，这个数被除之后会剩余3；对于7来说，被除之后剩余2。所以说，我们当前得到的这个数是满足题目要求的一个数。但是这个数是不是最小的，那就不一定了。
 *  减去最小公倍数lcm（在比最小公倍数大的情况下）
    
    > x=128-105=23
    
    应该不能确定是不是最小的数，这个时候就要用到他们的最小公倍数了。最小公倍数顾名思义，一定是一个同时被几个数整除的最小的一个数，所以减去它剩余下来的余数还是符合题意要求的。当然也同样可以运用定理1来解释，只不过是加法变成了减法，道理还是一样的。当然具体要不要减还是要看和lcm的大小关系的。

那么满足题意得最小的数就是23了。

总之，就是已知m1,m2,m3是两两互质的正整数，求最小的正整数x，使它被m1,m2,m3除所得的余数分别是c1,c2,c3。孙子定理的思想便是线分别求出被其中数mi整除余1而被两外两个数整除的数Mi(i=1,2,3)，则所求数之一的便是c1M1+c2M2+c3M3。由此我们可以得到n个两两互质数的情况。证明上面已经一步一步给出。

那么对于这道题的代码就是

//
    //  main.cpp
    //  数论の重逢
    //
    //  Created by Angus on 2017/12/21.
    //  Copyright © 2017年 Angus. All rights reserved.
    //
    
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    
    using namespace std;
    
    //参数可为负数的扩展欧几里德定理
    void exOJLD(long long a, long long b, long long &x, long long &y){
        //根据欧几里德定理
        if(b == 0){
       //任意数与0的最大公约数为其本身。
            x = 1;
            y = 0;
        }
        else{
            long long x1, y1;
            exOJLD(b, a % b, x1, y1);
            if(a*b < 0) {
       //异号取反
                x = - y1;
                y = a / b * y1 - x1;
            }else{
       //同号
                x = y1;
                y = x1 - a / b * y1;
            }
        }
    }
    
    //剩余定理
    long long calSYDL(long long a[], long long m[], long long k){
        long long N[k];//这个可以删除
        long long mm = 1;//最小公倍数
        long long result = 0;
        for(long long i = 0; i < k; i++){
            mm *= m[i];
        }
        for(long long j = 0; j < k; j++){
            long long L, J;
            exOJLD(mm / m[j], -m[j], L, J);
            N[j] = m[j] * J + 1;//1
            N[j] = mm / m[j] * L;//2 【注】1和2这两个值应该是相等的。
            result += N[j] * a[j];
        }
        return (result % mm + mm) % mm;//落在(0, mm)之间，这么写是为了防止result初始为负数，本例中不可能为负可以直接 写成：return result%mm;即可。
    }
    
    int main(int argc, const char * argv[]) {
        // insert code here...
        long long p, e, i;
        while(~scanf("%lld%lld%lld", &p, &e,&i)) {
            long long a[3] = {p, e, I};//余数
            long long m[3] = {
       25, 28, 33};//除数
            printf("%lld\n",calSYDL(a, m, 3));//余数数组，除数数组，数组元素个数
        }
        return 0;
    }

--------------------

参考资料  
[中国剩余定理(孙子定理)详解][Link 2]  
[中国剩余定理(孙子定理)的证明和c++求解][c]

[Link 1]: https://buaacoding.cn/problem/620/index
[Link 2]: https://www.cnblogs.com/freinds/p/6388992.html
[c]: http://blog.csdn.net/hard_man/article/details/7732795