/*
该题使用的是扩展欧几里德算法,求模线性同余方程;
分析题目:以题目输出结果为例 ,要求得到一个整数X可以满足 X % a = r,a,r,为数组名;
设数组元素为两个时,
列出方程:X % a1 = r1;
X % a2 = r2;
可得出: a1*k1 + r1 = X;
a2*k2 + r2 = X;
合并方程:a1*k1 + r1 = a2*k2 + r2,经变形得
a1*k1 - a2*k2 = r2 - r1;
由扩展欧几里德算法公式:ax + by = c;
得到 k1, 再将 k1 反代入 a1*k1 + r1 = X 中得到 X ,
于是X就是这两个方程的一个特解,通解就是 X'=X+k*LCM(m1,m2)
这个式子再一变形,得 X' mod LCM(m1,m2)=X
这个方程一出来,说明我们实现了(1)(2)两个方程的合并。
令 M=LCM(m1,m2),R=r2-r1
就可将合并后的方程记为 X mod M = R。
*/
#include<iostream>
#define LL long long
using namespace std;
void gcd(LL a,LL b,LL &d,LL &x,LL &y){
if(!b){
d=a;x=;y=;
}
else{
gcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
LL get(LL *a,LL *r,int n){
LL A=a[],R=r[],d,x,y,sum,T;
for(int i=;i<n;i++){
gcd(A,a[i],d,x,y);
if((r[i]-R)%d!=)
return -;
x=x*(r[i]-R)/d;
T=a[i]/d;
x=x%T;//得到x的最小整数解
R=A*x+R;//将x代入回原方程
A=A*a[i]/d;//求最小公倍数
R=R%A;
}
return R>?R:R+A;
}
int main(){
int n;
while(cin>>n){
LL a[],r[];
for(int i=;i<n;i++){
cin>>a[i]>>r[i];
}
cout<<get(a,r,n)<<endl;
}
return ;
}
05-02 04:18