中国剩余定理（孙子定理）

不念不忘少年蓝@ 2022-06-12 03:17 384阅读 0赞

中国剩余定理，也称孙子定理，是中国古代求解一次同余式组的重要方法。

《孙子算经》里面的"物不知数"说的是这样的一个题目：一堆东西不知道具体数目，3个一数剩2个，5个一数剩3个，7个一数剩2个，问一共有多少个。  
书里面给了计算过程及答案：70\*2 + 21\*3 + 15\*2 -105\*2 = 23。

它的计算思路如下：  
70是能被5或7整除的数字，但是除以3正好余1。  
21是能被3或7整除的数字，但是除以5正好余1。  
15是能被3或5整除的数字，但是除以7正好余1。  
所以若有数N = 70 \* N1 + 21 \* N2 + 15 \* N3(其中N,N1,N2,N3为正整数)，则整数N是符合题目要求的结果(mod3为N1，mod5为N2， mod7为N3)。  
我们把N1赋值2，N2赋值3，N3赋值2。  
则: N = 70\*2 + 21\*3 + 15\*2 = 233。  
但是3，5，7的最小公倍数为105。  
所以N + 105\*M均为正解。  
因此为了求得最小正整数解，我们需要用(N mod 105)也就是23了。

而中国剩余定理就是解决上述问题的通用方法，模板如下。

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    
    int exgcd(int a, int b, int &x, int &y)//拓展欧几里得 (可处理负数版本)
    {
    	if (b == 0)
    	{
    		x = 1;
    		y = 0;
    		return a;
    	}
    	int ans = exgcd(b, a%b, x, y);
    	int TT = x;
    	if (a*b < 0)
    	{
    		x = -y;
    		y = a / b*y - TT;
    	}
    	else
    	{
    		x = y;
    		y = TT - a / b*y;
    	}
    	return ans;//ans是a，b的最大公约数  
    }
    
    int chinasolve(int a[],int m[],int k)//除数即m数组必须都是素数
    {
    	int mm = 1;
    	int result = 0;
    	for (int i = 0; i < k; i++)
    	{
    		mm *= m[i];
    	}
    	for (int j = 0; j < k; j++)
    	{
    		int L, J;                     // Ni%mi=1↓     ↓因为Ni能被m1, m2,...,mi-1, mi+1,...,mk整除
    		exgcd(mm / m[j], -m[j], L, J);// mi*J + 1  =  mm/mi *L  ==> (-mi)*J + mm/mi*L = 1
    		result += (m[j] * J + 1)*a[j];//70*2 + 21*3 + 15*2 = 233。
    	}
    	return (result%mm + mm) % mm;//此处mm实际上是最小公倍数，但是因为m数组都是素数，所以最小公倍数就是mm
    }

a数组里存的是所要求的余数，m数组则是对应的除数。例如文章开头那道题，调用函数的方法如下。

int main()
    {  
        int a[3] = {2, 3, 2};  
        int m[3] = {3, 5, 7};      
        cout<<"结果:"<<calSYDL(a, m, 3)<<endl;  
    }

输出的结果便是满足题目要求的最小数，23。