1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include<iostream>
#include<cstdio>
using namespace std;
long long read()
{
long long x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
long long exgcd(long long A,long long B,long long &x,long long &y)
{
if(B==0)
{
x=1,y=0;
return A;
}
long long t=exgcd(B,A%B,x,y),tx=x;
x=y;
y=tx-(A/B)*y;
return t;
}
long long lcm(long long A,long long B)
{
long long tx,ty;
return (A*B)/exgcd(A,B,tx,ty);
}
const int N=100000+1000;
long long r[N],p[N];
int n;
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
p[i]=read(),r[i]=read();
long long R=r[1],P=p[1];
bool OK=true;
for(int i=2;i<=n;i++)
{
long long x,y,gcd=exgcd(P,p[i],x,y);
if((r[i]-R)%gcd!=0)
{
OK=false;
break;
}
long long t_P=P,t=p[i]/gcd;
x*=(r[i]-R)/gcd,P=lcm(P,p[i]),x=(x%t+t)%t;
R=((t_P*x)%P+R)%P;
}
if(OK==true)
printf("%lld\n",(R%P+P)%P);
else
printf("-1\n");
}
return 0;
}
|
