CRT是用于解一组同余方程：

$ x ≡ c1 ( mod\ m1)$

$ x ≡ c2 ( mod\ m2)$

...

$ x ≡ cn ( mod\ mn)$

当模数两两互质的时候，显然可以直接用朴素CRT合并

那当模数不互质的时候，就需要推一波式子采用扩展CRT了

考虑合并两个方程：

$ x ≡ c1 ( mod\ m1)$

$ x ≡ c2 ( mod\ m2)$

显然有$ x = c1+k1m1$, $ x = c2+k2m2$, 即$c1+k1m1=c2+k2m2$

移项得$ k1m1=k2m2+c2-c1$

我们令$ t=gcd(m1,m2)$, 则有$ \frac{m1}{t}k1=\frac{m2}{t}k2+\frac{c2-c1}{t}$

显然当且仅当$ t|c2-c1$时可以合并

此时有$ \frac{m1}{t}k1≡\frac{c2-c1}{t} (mod \frac{m2}{t})$

由于$ k1$的系数$ \frac{m1}{t}$和模数$ \frac{m2}{t}$互质，通过扩展欧几里得求得逆元$ inv$

则化简得$ k1≡\frac{c2-c1}{t}*inv \ (mod \frac{m2}{t})$

将$ k1$代回第一个方程得$ x≡(\frac{c2-c1}{t}*inv \ mod \frac{m2}{t})*m1+c1(mod \frac{m1*m2}{t})$

这是一个同余方程的形式，如此不断合并所有方程即可

时间复杂度:$ O$(方程数*$ log$(值域))

code：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define rt register int#define l putchar('\n')#define ll long long#define r read()using namespace std;inline ll read(){    register ll x = 0; char zf = 1; char ch;    while (ch != '-' && !isdigit(ch)) ch = getchar();    if (ch == '-') zf = -1, ch = getchar();    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x * zf;}void write(ll y){
   if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}void writeln(const ll y){write(y);putchar('\n');}int i,j,k,m,n,x,y,z,cnt,sum;struct calc{    ll c,m;}ans,now;inline ll mul(ll x,ll y,ll mod){    ll tmp=(x*y-(ll)((long double)x/mod*y+1e-8)*mod);    return tmp<0?tmp+mod:tmp;}ll gcd(ll x,ll y){
    return !y?x:gcd(y,x%y);}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 inv(ll A,ll p){    ll x,y;    exgcd(A,p,x,y);    return (x<=0)?(x+p):x;}calc operator &=(calc &x,calc y){    const ll t=gcd(x.m,y.m);    if(abs(y.c-x.c)%t){cout<<-1;exit(0);}    x.c=mul(mul((y.c-x.c)/t,inv(x.m/t,y.m/t),y.m),x.m,x.m/t*y.m)+x.c;    x.m=x.m/t*y.m;while(x.c<0)x.c+=x.m;}int main(){    n=read();    ans.m=read();ans.c=read();    for(rt i=1;i