刚学数论，萌新求助

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e6+10;

int n;
ll ai[N],mi[N];

ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b) {x=1,y=0; return a;}
	else 
	{
		ll d=exgcd(b,a%b,y,x);
		y-=a/b*x;
		return d;
	}
}

ll qmul(ll a,ll k,ll mod)//龟速乘
{
	ll res=0;
	while(k>0)
	{
		if(k&1) res=(res%mod+a%mod)%mod;
		a=(a%mod+a%mod)%mod;
		k>>=1;
	}
	return (res%mod+mod)%mod;
}

void excrt()
{
	bool flag=1;//是否有解
	ll a1=ai[1],m1=mi[1];
	for(int i=2;i<=n;i++)
	{
		ll a2=ai[i],m2=mi[i];
		ll k1,k2;
		ll d=exgcd(m1,-m2,k1,k2);
		if((a2-a1)%d!=0)//无解
		{
			flag=0;
			break;
		}
		ll t=m2/d;
		k1=qmul(k1,(a2-a1)/d,t);
		a1=m1*k1+a1;
		m1=(m1/d*m2>0?m1/d*m2:-(m1/d*m2));
	}
	if(flag) printf("%lld",(a1%m1+m1)%m1);
	else printf("-1");
}

int main()
{
#ifdef test
	freopen("P4777_15.in","r",stdin);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&mi[i],&ai[i]);
	excrt();
	return 0;
}