扩展中国剩余定理

$$\left\{\begin{matrix} x\equiv a_{1}\left ( mod \ m_{1} \right ) \\ x\equiv a_{2}\left ( mod \ m_{2} \right )\\ \cdots \\ x\equiv a_{n}\left ( mod \ m_{n} \right )\\ \end{matrix}\right.$$

不保证$m$两两互质

设已求出前$k$个方程的解，记为$x_{k}$
记$M_{k}=\prod _{i=1}^{k}m_{i}$
则$x_{k}+tM_{k}\left ( k \in\mathbb{Z} \right )$为前$k$个方程的通解

考虑第$k+1$个方程

$$x_{k}+tM_{k} \equiv a_{k+1} \left ( mod \ m_{k+1}\right )$$

用$exgcd$解出$t$
若无解则方程组无解
若有解则$x_{k+1}=x_{k}+tM_{k}$

#include<cstdio>
#define LL long long
const int N=100050;
LL n,x,y,a[N],m[N],M=1;
LL mul(LL a,LL b,LL mod)
{
    LL ret=0;
    for(;b;b>>=1)
    {
        if (b&1) ret=(ret+a)%mod;
        a=(a<<1)%mod;
    }
    return ret;
}
void exgcd(LL a,LL b,LL &x,LL &y)
{
    if (!b) {x=1,y=0;return;}
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL exCRT()
{
    LL M=m[1],ans=a[1];
    for(int i=2;i<=n;i++)
    {
        LL w=gcd(M,m[i]);
        LL c=(a[i]-ans)%m[i]+m[i];
        exgcd(M/w,m[i]/w,x,y);
        x=mul(x,c%m[i]/w,m[i]);
        ans+=x*M,M*=m[i]/w;
    }
    return (ans%M+M)%M;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&m[i],&a[i]);
    printf("%lld\n",exCRT());
    return 0;
}