当前位置:网站首页>Chinese Remainder Theorem (Sun Tzu theorem) principle and template code

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

2022-07-06 07:59:00 Alkali!

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

 Insert picture description here
 Insert picture description here


Template code

 Insert picture description here
 Insert picture description here
 Insert picture description here
 Insert picture description here
 Insert picture description here
 Insert picture description here

#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;
}
原网站

版权声明
本文为[Alkali!]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/02/202202131849187166.html