EXCRT

[EXCRT模板]

• 龟速乘

ll mul(ll a,ll b,ll p){ll ans=0;for(;b;b>>=1,a=(a+a)%p)if(b&1)ans=(ans+a)%p;return ans;}

• 扩欧

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

• EXCRT

ll CRT(){
	ll A1=a[1],B1=b[1],x,y;
	rep(i,2,n){
		ll tmp=((a[i]-A1)%b[i]+b[i])%b[i];
		ll d=exgcd(B1,b[i],x,y);
		if(tmp%d)return -1;
		x=mul(x,tmp/d,b[i]);
		A1+=B1*x,B1*=b[i]/d,A1=(A1%B1+B1)%B1;
	}return A1;
}

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define per(i,a,b) for(ll i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const ll N=1e6;
ll a[N],b[N],n;
inline ll read(){
	ll num=0;char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))num=num*10+ch-'0',ch=getchar();
	return num;
}
inline void Prll(ll x){if(x>9)Prll(x/10);putchar(x%10+'0');}
ll mul(ll a,ll b,ll p){ll ans=0;for(;b;b>>=1,a=(a+a)%p)if(b&1)ans=(ans+a)%p;return ans;}
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){x=1,y=0;return a;}
	ll d=exgcd(b,a%b,x,y);
	ll z=x;x=y,y=z-(a/b)*y;
	return d;
}
ll CRT(){
	ll A1=a[1],B1=b[1],x,y;
	rep(i,2,n){
		ll tmp=((a[i]-A1)%b[i]+b[i])%b[i];
		ll d=exgcd(B1,b[i],x,y);
		if(tmp%d)return -1;
		x=mul(x,tmp/d,b[i]);
		A1+=B1*x,B1*=b[i]/d,A1=(A1%B1+B1)%B1;
	}return A1;
}
int main()
{
	//freopen("a.in","r",stdin);
	n=read();rep(i,1,n)b[i]=read(),a[i]=read();
	cout<<CRT();
	return 0;
}