C++14(g++5.4) 解法, 执行用时: 132ms, 内存消耗: 1144K, 提交时间: 2019-08-24 17:11:26

#include<bits/stdc++.h>
using namespace std;
int a[100005],m[100005];
typedef long long LL;
int n;
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,y,x);y-=(a/b)*x;
	return d;
}
inline void excrt() {
	LL M=1,A=0;
	for (int i=1;i<=n;i++) {
		LL x,y,d=exgcd(M,m[i],x,y),mm=m[i]/d;
		if ((a[i]-A)%d) {puts("-1");return;}
		x=(x%mm+mm)%mm;
		LL k=(LL)((__int128)(a[i]-A)/d*x%mm+mm)%mm;
		LL nM=M*mm;
		A=(LL)((A+(__int128)k*M)%nM);
		M=nM;
	}
	printf("%lld\n",A);
}
int main(){
	
	while(~scanf("%d",&n)){
	for(int i=1;i<=n;i++)
		scanf("%d%d",&m[i],&a[i]);
	excrt();}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 178ms, 内存消耗: 392K, 提交时间: 2020-10-10 17:32:46

#include<cstdio>
#include<cstdlib>
#define ll long long
using namespace std;
bool sign;
ll k,R,A,r,a,x,y,Ax,d;
void euc(ll a,ll b,ll&x,ll&y){
	if(!b)
		if(Ax%a)sign=false;
		else x=Ax/(d=a),y=0;
	else{
		euc(b,a%b,y,x);
		if(sign)y-=x*(a/b);
	}
}int main(){
	while(scanf("%lld%lld%lld",&k,&A,&R)!=EOF){
		sign=true;
		for(ll i=1;i<k;i++){
			scanf("%lld%lld",&a,&r);
			if(sign){
				Ax=r-R,euc(A,a,x,y);
				if(!sign){
					R=-1;
					continue;
				}a/=d,x=(x%a+a)%a;
				R+=A*x,A=A*a;
				R=((R%A)+A)%A;
			}
		}printf("%lld\n",R);
	}return 0;
}