求解方程组
X%m1=r1
X%m2=r2
....
X%mn=rn
首先看下两个式子的情况
X%m1=r1
X%m2=r2
联立可得
m1*x+m2*y=r2-r1
用ex_gcd求得一个特解x'
得到X=x'*m1+r2
X的通解X'=X+k*LCM(m1,m2)
上式可化为：X'%LCM(m1,m2)=X
到此即完成了两个式子的合并，再将此式子与后边的式子合并，最后的得到的X'即为答案的通解，求最小整数解即可。
#include<stdio.h>
#include<string.h>
typedef long long ll;
ll ex_gcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=,y=;
return a;
}
ll ans=ex_gcd(b,a%b,y,x);
y-=a/b*x;
return ans;
}
int main(){
int n;
ll a,b,c1,c2,c,x,y,d;
while(~scanf("%d",&n)){
scanf("%lld%lld",&a,&c1);
int f=;
for(int i=;i<n;i++){
scanf("%lld%lld",&b,&c2);
d=ex_gcd(a,b,x,y);
c=c2-c1;
if(c%d) f=;
c/=d;ll t=b/d;
x=((x*c)%t+t)%t;
c1+=a*x;//X
a=a/d*b;//lcm
c1%=a;
}
if(c1<) c1+=a;
if(f) printf("%lld\n",c1);
else printf("-1\n");
}
return ;
}