1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=1e5+5; 5 ll a[N],mod[N],ans,n,mulsum=1; 6 ll read() 7 { 8 ll x=0,f=1;char ch=getchar(); 9 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 10 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} 11 return x*f; 12 } 13 ll exgcd(ll a, ll b, ll &x, ll &y) 14 { 15 if(!b) 16 { 17 x=1,y=0; 18 return a; 19 } 20 ll d=exgcd(b,a%b,x,y); 21 ll t=x; 22 x=y;y=t-a/b*y; 23 return d; 24 } 25 int main() 26 { 27 ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 28 n=read(); 29 for(int i=1;i<=n;i++)mod[i]=read(),a[i]=read(),mulsum*=mod[i]; 30 for(int i=1;i<=n;i++) 31 { 32 ll x,y; 33 ll mi=mulsum/mod[i]; 34 exgcd(mi,mod[i],x,y); 35 x=((x%mod[i])+mod[i])%mod[i]; 36 ans=(ans+(x*mi*a[i]))%mulsum; 37 } 38 cout<<ans<<"\n"; 39 return 0; 40 }