中国剩余定理，模数不互质的情况。
用数学归纳法两两式子解。
先用扩展欧几里得求出第一个方程的x通解。
然后与第二个联立，求出再第一个方程同解的集合内的情况下，x的通解。（注意要判是否有解）
以此类推。
注意防止整数溢出。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls (o<<1)
#define rs (o<<1|1)
#define pb push_back
//#define a(i,j) a[(i)*(m+2)+(j)] //m是矩阵的列数
const int M = 37;
/*
int head[M],cnt;
void init(){cnt=0,memset(head,0,sizeof(head));}
struct EDGE{int to,nxt,val;}ee[M*2];
void add(int x,int y,int z){ee[++cnt].nxt=head[x],ee[cnt].to=y,ee[cnt].val=z,head[x]=cnt;}
*/ll a[M],m[M];
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);
}
void exgcd(ll a,ll b, ll &x,ll &y)
{if(b==0){x=1,y=0;// a*1+b*0=gcd(a,0);return ;}exgcd(b,a%b,x,y);ll z=x;x=y,y=z-y*(a/b);return ;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);ll n;cin>>n;for(int i=1;i<=n;i++)cin>>m[i]>>a[i]; ll lm=m[1];ll x,y;bool f=true;//是否有解 exgcd(1,m[1],x,y);x=x*a[1];for(int i=2;i<=n;i++){ll tm=gcd(lm,m[i]);if((a[i]-x)%gcd(lm,m[i])!=0){f=false;break;}ll t;exgcd(lm,m[i],t,y);t=(t*(a[i]-x)/tm)%(m[i]/tm);//防止整数溢出 x=x+t*lm;lm=lm*m[i]/gcd(lm,m[i]);x%=lm;//防止整数溢出 }if(!f){cout<<-1<<endl;return 0;}cout<<(x%lm+lm)%lm<<endl;;return 0;
}