RT，前人 WA on #15 的基本都是没用快速/龟速乘或者快速/龟速乘写挂的，不知道哪里出锅了

#include <cstdio>
#define int long long

int gcd(int a,int b){
	return !b?a:gcd(b,a%b);
}

int lcm(int a,int b){
	return a/gcd(a,b)*b;
}

int fmul(int a,int p,int m){
	//龟速乘 
	int res=0;
	while(p){
		if(p&1) res=(res+a)%m;
		a=(a+a)%m;p>>=1;
	}
	return res;
}

struct pair{
	int x,y;
};

pair exgcd(int a,int b){
	if(!b) return (pair){1,0};
	pair k=exgcd(b,a%b);
	return (pair){k.y,k.x-a/b*k.y};
}

pair ind_equation(int a,int b,int c){
	//解不定方程 ax+by=c 
	pair res=exgcd(a,b);
	int d=c/gcd(a,b);
	return (pair){res.x*d,res.y*d};
}

const int N=1e5;

int a[N+1],m[N+1];

void merge(int i){
	//把第i个同余方程和第i+1个合并 
	int k=ind_equation(m[i],-m[i+1],a[i+1]-a[i]).x;
	int d=lcm(m[i],m[i+1]);m[i+1]=d;
	a[i+1]=((fmul(k,m[i],d)+a[i])%d+d)%d;
}

signed main()
{
	int n;scanf("%lld",&n);
	for(int i=1;i<=n;++i) scanf("%lld%lld",m+i,a+i),a[i]%=m[i];
	for(int i=1;i<n;++i) merge(i);
	printf("%lld",a[n]);
}