1 #include <iostream>
2 #include <algorithm>
3 #include <cstdio>
4 using namespace std;
5 const int N=107;
6 int m[N];// 质除数
7 int p[N];// 余数
8 int e_gcd (int a,int b,int &x,int &y) {
9 if (b==0) {
10 x=1;
11 y=0;
12 return a;
13 } // a*x1+b*y1=1;
14 // a*y2+b*(x2-(a/b)*y2)=1
15 int d=e_gcd (b,a%b,y,x);// 作用 :求出x2与y2 并且使y1=x2; x1=y2;
16 y=y-(a/b)*x;//y1=x2-(a/b)*y2;
17 return d;
18 }
19 int china (int m[],int p[],int n) {
20 int M=1;
21 for (int i=1;i<=n;i++)
22 M=M*m[i];
23 int ans=0;
24 for (int i=1;i<=n;i++) {
25 int a=M/m[i];
26 int x,y;
27 e_gcd (a,m[i],x,y);
28 x=x*p[i]*a;//important!!!
29 ans+=(x+M)%M;
30 }
31 return ans%M;
32 }
33 int main ()
34 {
35 int n;
36 cin>>n;
37 for (int i=1;i<=n;i++) {
38 cin>>m[i]>>p[i];
39 }
40 int ans=china (m,p,n);
41 cout<<ans<<endl;
42 return 0;
43 }