中国剩余定理【数论】

 今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

 

有多个方程，只有一个变量，可以用中国剩余定理来做。

void exgcd(int a,int b,int &x,int &y)
{
    if(b==0){ x=1; y=0; return;}
    exgcd(b,a%b,x,y);
    int tp=x;
    x=y; y=tp-a/b*y;
}

int china()
{
    int ans=0,lcm=1,x,y;
    for(int i=1;i<=k;++i) lcm*=b[i];
    for(int i=1;i<=k;++i)
    {
        int tp=lcm/b[i];
        exgcd(tp,b[i],x,y);
        x=(x%b[i]+b[i])%b[i];//x要为最小非负整数解
        ans=(ans+tp*x*a[i])%lcm;
    }
    return (ans+lcm)%lcm;
}

https://www.cnblogs.com/freinds/p/6388992.html

https://blog.csdn.net/niiick/article/details/80229217