将同余方程改写等式,用exgcd合并即可
#include<bits/stdc++.h>
#define int __int128
using namespace std;
int rd(){
int ret=0,f=1;char c;
while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
while(isdigit(c))ret=ret*10+c-'0',c=getchar();
return ret*f;
}
void exgcd(int A, int B, int &x, int &y) {
if(!B) x = 1, y = 0;
else exgcd(B, A%B, y, x), y -= (A/B) * x;
}
const int MAXN = 100005;
int n;
signed main(){
n=rd();
int preans=0,lcm=1;
for(int i=1;i<=n;i++){
int p,r,x,y;
p=rd();r=rd();
int g=__gcd(lcm,p);
exgcd(lcm,p,x,y);
if((r-preans)%g) return 0;
int stp=p/g;
x%=stp;
if(x<0) x+=stp;
x*=(r-preans)/g;
preans+=x*lcm;
lcm*=p/g;
preans%=lcm;
if(preans<0) preans+=lcm;
}
cout<<(long long)preans;
return 0;
}