Chinese Remainder Theorem (Sun Tzu theorem) principle and template code

Background

Sun Tzu theorem is ancient China Solve the group of primary congruences Methods . Is an important theorem in number theory . Also known as Chinese Remainder Theorem . The system of Linear Congruence Equations with one variable can be seen in the northern and Southern Dynasties of China （ A.D. 5 century ） Mathematical works of 《 Sun Tzu's Sutra 》 Volume II question 26 , be called “ I don't know the number of things ” problem , The text is as follows ：
I don't know the number of things , Two out of three , Three out of five , Two of the seven . Query geometry ？ namely , An integer divided by three and two , Divide by five and three , Divide by seven and two , Find this integer .《 Sun Tzu's Sutra 》 The problem of Congruence Equations is mentioned for the first time , And the solution of the above specific problems , Therefore, the Chinese remainder theorem will also be called the Sun Tzu theorem in the Chinese mathematical literature .

---

principle

---

Template code

#include<iostream>
using namespace std;
typedef long long LL;  // The data range is quite large , Here we use long long
LL exgcd(LL a,LL b,LL &x,LL &y)   // extended euclidean algorithm 
{
    
    if(!b)
    {
    
        x=1,y=0;
        return a;
    }
    LL ans=exgcd(b,a%b,x,y);
    LL t=x;
    x=y;
    y=t-a/b*y;
    return ans;
}
LL mod(LL a,LL b)    // Guarantee a%b The value after taking the module must be non negative 
{
    
    return (a%b+b)%b;
}
int n;
int main()
{
    
    scanf("%d",&n);
    LL m1,a1,m2,a2,k1,k2;
    scanf("%lld%lld",&a1,&m1);
    for(int i=1;i<n;i++)
    {
    
        scanf("%lld%lld",&a2,&m2);
        LL d=exgcd(a1,-a2,k1,k2);
        if((m2-m1)%d)  // If it's not divisible , Explain that there is no solution 
        {
    
            printf("%d",-1);
            return 0;
        }
        k1=mod(k1*(m2-m1)/d,abs(a2/d));  // Take mold at any time , Ensure the minimum number in the calculation process , Give Way k The value of is always optimal 
        m1=k1*a1+m1;       // At this time m and a After the merger x In the expression m and a
        a1=abs(a1/d*a2);   //
    }
    printf("%lld",mod(m1,a1));   // The answer is this 
    return 0;
}