互质

llm[N],p[N];//p是质数，m是余数llExgcd(lla,llb,ll&x,ll&y){if(b==0){x=1;y=0;returna;}llx1,y1;lld=Exgcd(b,a%b,x1,y1);x=y1;y=x1-a/b*y1;returnd;}llCrt(ll*m,ll*p,intl){llres=0,n=1,x,y;for(inti=0;i<l;i++)n*=p[i];for(inti=0;i<l;i++){llt=n/p[i];lld=Exgcd(t,p[i],x,y);res=(res+m[i]*t%n*x%n)%n;}return(res%n+n)%n;}

非互质

#include<cstdio>//*m模数*a余数#include<iostream>#include<algorithm>#include<cstring>#include<string>usingnamespacestd;typedeflonglongll;voidexgcd(lla,llb,ll&x,ll&y){if(!b){x=1;y=0;return;}exgcd(b,a%b,x,y);lltemp=x;x=y;y=temp-(a/b)*y;}llinv(lla,llb){lld=__gcd(a,b);if(d!=1)return-1;llx,y;exgcd(a,b,x,y);return(x%b+b)%b;}boolmerge(lla1,llm1,lla2,llm2,ll&a3,ll&m3){lld=__gcd(m1,m2);llc=a2-a1;if(c%d)returnfalse;c=(c%m2+m2)%m2;m1/=d;m2/=d;c/=d;c*=inv(m1,m2);c%=m2;c*=m1*d;c+=a1;m3=m1*m2*d;a3=(c%m3+m3)%m3;returntrue;}llCRT(ll*a,ll*m,lln){lla1=a[1],m1=m[1];for(lli=2;i<=n;i++){lla2=a[i],m2=m[i];llm3,a3;if(!merge(a1,m1,a2,m2,a3,m3))return-1;a1=a3;m1=m3;}return(a1%m1+m1)%m1;}