解题思路

扩展 $crt​$，就是中国剩余定理在模数不互质的情况下，首先对于方程

​     $\begin{cases} x\equiv a_1\mod m_1\\x\equiv a_2\mod m_2\end{cases}$

来说，可以将其写为：

$\begin{cases} x=k_1*m_1+a_1\\x=k_2*m_2+a_2\end{cases}$

然后联立方程：

​     $k_1*m_1+a_1=k_2*m_2+a_2$

$\Leftrightarrow -k_1*m_1+k_2*m_2=a_1-a_2$

a这样的话形式就很像$exgcd$ 了，可以$exgcd$求出$k_1'*m_1+k_2'*m_2=gcd(m_1,m_2)$的$k_1'$了，然后若$(a_1-a_2)\%gcd(m_1,m_2)\neq 0$，则无解。然后让方程两边同时乘$(a_1-a_2)/gcd(m_1,m_2)$，就可以求出$k_1$了，最后再带入原式可以求出$x$的值，这个$x$记为$x_0$ ，即为满足上面两个方程的一个解，然后将这两个方程

合并成一个方程：$x\equiv x_0\mod lcm(m_1,m_2)$，之后就可以一直合并就行了。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int MAXN = 100005;typedef long long LL;//typedef __int128 LL;inline LL rd(){    LL x=0,f=1;char ch=getchar();    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}    return f?x:-x;}int n;LL a[MAXN],b[MAXN],M,R;LL slow_mul(LL x,LL y,LL mod){    LL ret=0;    for(;y;y>>=1){        if(y&1) ret=(ret+x)%mod;        x=(x+x)%mod;    }    return ret;}LL exgcd(LL a,LL b,LL &x,LL &y){    if(!b) {x=1;y=0;return a;}    LL now=exgcd(b,a%b,x,y);    LL t=x;x=y;y=t-(a/b)*y;    return now;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++) a[i]=rd(),b[i]=rd();    M=a[1];R=b[1];LL x,y,d,now;    for(int i=2;i<=n;i++){        d=exgcd(M,a[i],x,y);//        if((R-r[i])%d!=0) puts("-1");        now=((R-b[i])%a[i]+a[i])%a[i];        x=slow_mul(x,now/d,a[i]);R-=M*x;        M=M*(a[i]/d);R=(R%M+M)%M;    }    printf("%lld",(R%M+M)%M);    return 0;}