【4.6 中国剩余定理详解】

$更好的阅读体验$

概念

• 若存在整数$m_1,m_2,m_3\dots m_n$两两互质，则对于任意的整数$a_1,a_2,a_3\dots a_n$，一元线性同余方程组$(S)$有通解

• $$(S):\{\begin{array}{l}x\equiv a_1(mod{m}_1)\\ x\equiv a_2(mod{m}_2)\\ x\equiv a_3(mod{m}_3)\\ \dots \\ x\equiv a_n(mod{m}_n)\end{array}$$

思想

• 对于$(S)$其中的两个式子进行合并

• $$\{\begin{array}{l}x\equiv a_1(mod{m}_1)\\ x\equiv a_2(mod{m}_2)\end{array}\Rightarrow \{\begin{array}{l}x=k_1{m}_1+a_1\\ x=k_2{m}_2+a_2\end{array}$$

• 将等价转换后的两式进行联立，化简得$k_1{m}_1+k_2(-m_2)=a_2-a_1①$

• 由扩展欧几里得算法可以得到一组解$({k_1}^{\prime },{k_2}^{\prime })$，使得：${k_1}^{\prime }{m}_1+{k_2}^{\prime }(-m_2)=gcd(m_1,-m_2)$

• 若$gcd(m_1,-m_2)$不能整除$a2-a1$，则无解，否则有通解

• 设$gcd(m_1,-m_2)=d,y=\frac{(a_2-a_1)}{d}$

• 由扩展欧几里得算法的推论可知：$\{\begin{array}{l}{k}_1={k_1}^{\prime }y\\ k_2={k_2}^{\prime }y\end{array}$

• 引入通解$\{\begin{array}{l}{k}_1=k_1+k\frac{m_2}{d}\\ k_2=k_2+\frac{m_1}{d}\end{array}$，$k\in \mathbb{Z}$

• 将通解带入$①$得$(k_1+k\frac{m_2}{d})m_1+(k_2+k\frac{m_1}{d})(-m_2)=a_2-a_1$

• 化简得$k_1{m}_1+k_2(-m_2)=a_2-a_1$和$①$相同，故成立

• 重复上述步骤，不断合并剩余的式子，即可得到最终的通解

---

例题 表达整数的奇怪方式

原题链接

描述

给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn，求一个最小的非负整数 x，满足 ∀i∈[1,n],x≡mi(mod ai)。

输入格式
第 1 行包含整数 n。

第 2…n+1 行：每 i+1 行包含两个整数 ai 和 mi，数之间用空格隔开。

输出格式
输出最小非负整数 x，如果 x 不存在，则输出 −1。
如果存在 x，则数据保证 x 一定在 64 位整数范围内。

数据范围
1≤ai≤231−1,
0≤mi<ai
1≤n≤25
输入样例：

2
8 7
11 9

输出样例：

31

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

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

LL gcd(LL a,LL b){
    
    return b ? gcd(b,a%b) : a;
}

int main(){
    
    
    int n;
    
    cin>>n;
    
    LL x=0,m1,a1;  //第一个方程的系数 备份数据
    
    cin>>m1>>a1;  //先输入第一个方程
    
    for(int i=0;i<n-1;i++){
      //合并接下来的n-1个方程
        
        LL m2,a2;
        
        cin>>m2>>a2;
        
        LL k1,k2;
        
        LL d=gcd(m1,m2);
        
        exgcd(m1,m2,k1,k2);
        
        if((a2-a1)%d){
      //此时无解
            
            x=-1;
            break;
            
        }
        
        k1*=(a2-a1)/d;//特解
        k1=(k1%(m2/d)+m2/d)%(m2/d);  //让特解k1取到最小正整数解
        
        x=k1*m1+a1;
        
        LL m=abs(m1/d*m2);
        a1=k1*m1+a1;  
        
        m1=m;
        
    }
    
    if(x!=-1) x=(a1%m1+m1)%m1   //当循环结束时，此时的值应该与最小公倍数取模,以求得最小正整数解
    
    cout<<x<<endl;
    
    return 0;
    
}

---