from CRT to EXCRT

模板洛谷P4777

#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
long long a[100005],b[100005];
void gcd(ll a,ll b,ll& x,ll& y,ll& d)
{
	if(!b)
	x=1,y=0,d=a;
	else
	gcd(b,a%b,y,x,d),y-=a/b*x;
}
int main()
{
	long long t;
	cin>>t;
	for(int i=1;i<=t;i++)
	cin>>a[i]>>b[i];
	for(int i=1;i<t;i++)
	{
		ll A=a[i],B=a[i+1],C=(b[i+1]-b[i]),x,y,d=__gcd(A,B);
		if(C%d)
		return cout<<"-1",0;
		A/=d,B/=d,C/=d;
		gcd(a[i],a[i+1],x,y,d);
		x=(x*C%B+B)%B;
		a[i+1]=a[i]/d*a[i+1];
		b[i+1]=(a[i]*x%a[i+1]+b[i])%a[i+1];
	}
	cout<<b[t];
}