[4.6 detailed explanation of Chinese remainder theorem]

$Better\; reading\; experience$

Concept

• If there is an integer $m_1,m_2,m_3\dots m_n$ The two are mutual , Then for any integer $a_1,a_2,a_3\dots a_n$, Univariate Linear Congruence Equations $(S)$ Have a general solution

• $$(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}$$

thought

• about $(S)$ The two formulas are merged

• $$\{\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}$$

• Combine the two formulas after equivalent conversion , Simplify to $k_1{m}_1+k_2(-m_2)=a_2-a_1①$

• A set of solutions can be obtained from the extended Euclidean algorithm $({k_1}^{\prime },{k_2}^{\prime })$, bring ：${k_1}^{\prime }{m}_1+{k_2}^{\prime }(-m_2)=gcd(m_1,-m_2)$

• if $gcd(m_1,-m_2)$ Not divisible $a2-a1$, There is no solution. , Otherwise, there is a general solution

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

• From the inference of extended Euclidean algorithm ：$\{\begin{array}{l}{k}_1={k_1}^{\prime }y\\ k_2={k_2}^{\prime }y\end{array}$

• Introduce general solution $\{\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}$

• Bring the general solution into $①$ have to $(k_1+k\frac{m_2}{d})m_1+(k_2+k\frac{m_1}{d})(-m_2)=a_2-a_1$

• Simplify to $k_1{m}_1+k_2(-m_2)=a_2-a_1$ and $①$ identical , Therefore, it is established that

• Repeat the above steps , Continue to merge the remaining formulas , You can get the final general solution

---

Example Strange way to express integers

Original link

describe

Given 2n It's an integer a1,a2,…,an and m1,m2,…,mn, Find the smallest nonnegative integer x, Satisfy ∀i∈[1,n],x≡mi(mod ai).

Input format
The first 1 Row contains integer n.

The first 2…n+1 That's ok ： Every time i+1 Line contains two integers ai and mi, The numbers are separated by spaces .

Output format
Output the minimum nonnegative integer x, If x non-existent , The output −1.
If there is x, Then the data guarantee x It must be 64 Bit integer range .

Data range
1≤ai≤231−1,
0≤mi<ai
1≤n≤25
sample input ：

2
8 7
11 9

sample output ：

31

Code

#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;  // The coefficients of the first equation   The backup data 
    
    cin>>m1>>a1;  // First enter the first equation 
    
    for(int i=0;i<n-1;i++){
      // Merge the following n-1 An equation 
        
        LL m2,a2;
        
        cin>>m2>>a2;
        
        LL k1,k2;
        
        LL d=gcd(m1,m2);
        
        exgcd(m1,m2,k1,k2);
        
        if((a2-a1)%d){
      // There is no solution at this time 
            
            x=-1;
            break;
            
        }
        
        k1*=(a2-a1)/d;// Special solution 
        k1=(k1%(m2/d)+m2/d)%(m2/d);  // Jean texie k1 Get the minimum positive integer solution 
        
        x=k1*m1+a1;
        
        LL m=abs(m1/d*m2);
        a1=k1*m1+a1;  
        
        m1=m;
        
    }
    
    if(x!=-1) x=(a1%m1+m1)%m1   // When the loop ends , The value at this time should be modular with the least common multiple , To find the minimum positive integer solution 
    
    cout<<x<<endl;
    
    return 0;
    
}

---