记录编号	281389	评测结果	AAAAAAAAAA
题目名称	韩信点兵	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2016-07-11 18:32:48	内存使用	0.31 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
typedef  long long LL;
LL people,n,su[2000],yu[2000],x,y,c,d,M=1,ans=0,em;
LL gcd(LL a,LL b,LL &x,LL &y,LL&d)
{
	if(b==0){d=a,x=1,y=0;}
	else{gcd(b,a%b,y,x,d);y-=x*(a/b);}
}
int main()
{
	freopen("HanXin.in","r",stdin);freopen("HanXin.out","w",stdout);
	cin>>people>>n;
	for(LL i=0;i<n;i++){
	cin>>su[i]>>yu[i];
		M*=su[i];
	}
	for(LL i=0;i<n;i++){
		em=M/su[i];
		x=0,y=0,d=0,c=1;
		gcd(em,su[i],x,y,d);
		ans+=( (x*em*yu[i])+M )%M;
	}
	ans=(ans+M )%M;
	if(ans>people){
		puts("-1");return 0;}
	while(ans<people)ans+=M;
	ans-=M;
	cout<<people-ans;
	return 0;
}
/*
1000000 4
3 0
2 0
5 4
7 0   ans=106;
100000000 5
1291 960
2039 252
337 311
389 277
2 1
 ans= -1;
1500 3
3 2
5 4
7 6
ans=31;
1000000000000 3
9871 1528
162731 5773
617 222
ans=443683241159;
*/