excrt模板
我们知道，crt无法处理模数不两两互质的情况
然鹅excrt可以
设当前解到第 i 个方程
设$M=\prod_{j=1}^{i-1}b[j]$ ,$ res$是前$ i-1 $个方程的最小解
则$ res+x*M$ 是前 $i-1 $个方程的通解
那么我们求的就是
$res+x*M ≡ a[i] (mod b[i])$
$<=> x*M - y*b[i] = a[i]-res$
用exgcd求出的解为 t （当且仅当 gcd(M,b[i])∣t 时有解）
x的一个解=$ t /gcd(M,b[i])*(a[i]-res)$
最小解=$ x\%( b[i] / gcd(M,b[i]) )$
∴$res=(res+x*M)\%( M=M*b[i] )$
如此递推
end.
poj2891 有多组数据，请自行修改（poj只能用 I64d 来着（大雾））
#include<cstdio>
#include<cctype>
using namespace std;
typedef long long ll;
char c;template<typename T>void read(T &x){
c=getchar(); x=;
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();
}
ll mod(ll x,ll p) {return x< ?x+p:x;}
ll mul(ll x,ll y,ll p){
ll tmp=x*y-(ll)((long double)x/p*y+1.0e-8)*p;
return mod(tmp,p);
}ll g,a[],b[];
void exgcd(ll a0,ll b0,ll &x,ll &y){
if(!b0) x=,y=,g=a0;
else exgcd(b0,a0%b0,y,x),y-=x*(a0/b0);
}int n;
ll excrt(){
ll res=a[],M=b[],x,y,c,t,B;
for(int i=;i<=n;++i){
B=b[i];
c=mod((a[i]-res)%B,B);
exgcd(M,B,x,y); t=B/g;
if(c%g) return -;
x=mul(x,c/g,t=B/g); 快速乘取模
res+=x*M; M*=t;
res=mod(res%M,M);
}return res;
}
int main(){
read(n);
for(int i=;i<=n;++i) read(b[i]),read(a[i]);
printf("%lld",excrt());
return ;
}