记录编号	423696	评测结果	AAAAAAAAAA
题目名称	2160.丧心病狂的韩信大点兵	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-07-12 13:57:26	内存使用	0.00 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long L;
int m;
L a[21],mod[21];
inline L gcd(L a,L b){
	return a%b?gcd(b,a%b):b;
}
inline L ext_gcd(L a,L b,L &x,L &y){
	if(b==0){
		x=1;
		y=0;
		return a; 
	}
	L gcd(ext_gcd(b,a%b,x,y));
	L tmp(x);
	x=y;
	y=tmp-(a/b)*y;
	return gcd;
}
inline L ny(L a,L b){
	L x,y;
	L gcd(ext_gcd(a,b,x,y));
	if(gcd!=1)
		return -1;
	return (x%b+b)%b;
}
inline bool merge(L a1,L m1,L a2,L m2,L &a3,L &m3){
	L d(gcd(m1,m2));
	L c=a2-a1;
	if(c%d)
		return false;
	c=(c%m2+m2)%m2;
	m1/=d;
	m2/=d;
	c/=d;
	c*=ny(m1,m2);
	c%=m2;
	c*=m1*d;
	c+=a1;
	m3=m1*m2*d;
	a3=(c%m3+m3)%m3;
	return true;
}
L CRT(L a[],L m[],int n){
	L a1(a[1]),m1(m[1]);
	for(int i=2;i<=n;i++){
		L a2(a[i]),m2(m[i]),a3,m3;
		if(!merge(a1,m1,a2,m2,a3,m3))
			return -1;
		a1=a3;
		m1=m3;
	}
	return (a1%m1+m1)%m1;
}
inline int gg(){
	freopen("weakhanxin.in","r",stdin);
	freopen("weakhanxin.out","w",stdout);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
		scanf("%lld%lld",&mod[i],&a[i]);
	printf("%lld",CRT(a,mod,m));
}
int k(gg());
int main(){;}