Summary of Chinese remainder theorem

1. Grandson's question

Earliest , stay 《 Sun Tzu's Sutra 》 There is such a problem ：“ I don't know how many things there are today , Two out of three , Three out of five , Two of the seven , Query geometry ？ In colloquial terms, it means , Now there is a number I don't know , Only know this number divided by 3 more than 2, Divide 5 more than 3, Divide 7 more than 2, What is this number ？

The above problem can be transformed into the following equation system :

Among them the x It's the number we require . The Chinese remainder theorem is used to solve the above form of equations x Solution .

2. Chinese remainder theorem formula

Set positive integers m1,m2,....,mk pairwise coprime , Then Congruence Equations :

 3. Solve examples

AcWing 204 Strange way to express integers

Their thinking ：

  The code is as follows ：

#include<iostream>
using namespace std;
typedef long long ll;// Prevent data overflow
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}// extended euclidean algorithm
int main()
{
    int n;
    cin>>n;
    bool flag=true;// Is there the smallest x value
    ll a1,m1;
    cin>>a1>>m1;
    for(int i=0;i<n-1;i++)
    {
        ll a2,m2;
        cin>>a2>>m2;
        ll k1,k2;
        ll d=exgcd(a1,a2,k1,k2);// Find the greatest common divisor
        if((m2-m1)%d)// If m2-m1 No a1,a2 Multiple of the greatest common divisor of
        {
            flag=false;
            break;
        }
        k1*=(m2-m1)/d;// because m2-m1 For the greatest common divisor d Expanded n times , therefore k1 It also needs to be expanded
        ll t=a2/d;
        k1=(k1%t+t)%t;// This problem is to find the minimum x, So find the smallest k1 value
        m1=a1*k1+m1;// use m1 To represent the current x Value
        a1=abs(a1/d*a2);// Find out a1,a2 The least common multiple of
    }
    if(flag)  // If it exists, output the smallest x value
       cout<<(m1%a1+a1)%a1<<endl;
    else
       puts("-1");
      return 0;
}