记录编号	137879	评测结果	AAAAAAAAAA
题目名称	韩信点兵	最终得分	100
用户昵称	Iostream3100	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2014-11-05 13:06:37	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
LL N,M,ans,m[100],a[100],MOD[101],x=10000000000000;
LL gcd(LL a,LL b){ return b==0? a: gcd(b,a%b); }
LL lcd(LL a,LL b){ return a*b/gcd(a,b); }
LL extend_gcd(LL a,LL b,LL &x, LL &y){
	if(!b){
		x=1;
		y=0;
		return a;
	}
	else{
		LL r=extend_gcd(b,a%b,y,x);
		y-=x*(a/b);
		return r;
	}
}
LL CRT(LL a[],LL m[],LL N){
	LL MM=1;
	for(int i=1;i<=N;++i) MM*=m[i];
	LL ret=0;
	for(int i=1;i<=N;++i){
		LL x,y;
		LL tm=MM/m[i];
		extend_gcd(tm,m[i],x,y);
		ret=(ret+tm*x*a[i])%MM;
	}
	return (ret+MM)%MM;
}
int main(){
	freopen("HanXin.in","r",stdin);
	freopen("HanXin.out","w",stdout);
	cin>>N>>M;
	for(LL i=1;i<=M;++i){
		cin>>m[i]>>a[i];
		MOD[i]=(N%m[i]+m[i]-a[i])%m[i];
	}
	x=CRT(MOD,m,M);
	if(x<=N) cout<<x<<endl;
	else cout<<-1<<endl;
}