记录编号	230766	评测结果	AAAAAAAAAA
题目名称	丧心病狂的韩信大点兵	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2016-02-23 17:23:22	内存使用	0.28 MiB

//标准的模线性方程组合并
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
LL realmod(LL a,LL m){
	a%=m;
	if(a<0) a+=m;
	return a;
}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
void extend_gcd(LL a,LL b,LL &x,LL &y,LL &d){
	if(!b){d=a;x=1;y=0;}
	else{extend_gcd(b,a%b,y,x,d);y-=x*(a/b);}
}
LL linear_solve(LL a,LL b,LL m){//解ax=b (mod m)
	LL x,y,d;
	extend_gcd(a,m,x,y,d);
	if(b%d) return -1;
	else return realmod(b/d*x,m);
}
bool linear_merge(LL a1,LL m1,LL a2,LL m2,LL &a,LL &m){
	//设x=k1m1+a1=k2m2+a2
	//k1m1=a2-a1 (mod m2)
	LL d=gcd(m1,m2);
	//k1(m1/d)=(a2-a1)/d (mod m2/d)
	//以保证k1的唯一性
	if((a2-a1)%d) return false;
	LL km=linear_solve(m1/d,(a2-a1)/d,m2/d);//km是k1模m2/d的值
	//设k1=km+t*(m2/d),代入x=k1m1+a1
	m=m1/d*m2;
	a=realmod(a1+km*m1,m);
	return true;
}
LL solve(LL n,LL *a,LL *m){//求解模线性方程组
	LL A=0,M=1;
	for(int i=1;i<=n;i++){
		if(!linear_merge(A,M,a[i],m[i],A,M)) return -1;
	}
	if(!A) A=M;
	return A;
} 
const int SIZE=110;
LL M;
LL P[SIZE],A[SIZE];
void read(void){
	cin>>M;
	for(int i=1;i<=M;i++){
		cin>>P[i]>>A[i];
	}
}
int main(){
	freopen("weakhanxin.in","r",stdin);
	freopen("weakhanxin.out","w",stdout);
	read();
	LL ans=solve(M,A,P);
	cout<<ans<<endl;
	return 0;
}