记录编号	157929	评测结果	AAAAAAAAAA
题目名称	韩信点兵	最终得分	100
用户昵称	ggwdwsbs	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2015-04-11 16:48:33	内存使用	0.29 MiB

#include<stdio.h>
long long gcd(long long x,long long y)
{
	if(y==0) return x;
	else return gcd(y,x%y);
}
long long exgcd(long long a,long long b,long long &d,long long &x,long long &y)
{
	if(!b)
	{
		d=a;
		x=1;
		y=0;
	}
	else
	{
		exgcd(b,a%b,d,y,x);
		y-=x*(a/b);
	}
}
long long abs(long long x)
{
	if(x>0) return x;
	else return -x;
}
long long a,b,d1,x1,y1;
long long get(long long a,long long b)
{
	exgcd(a,-b,d1,x1,y1);
	x1=x1*(1/d1);
	long long a1=a/d1;
	long long b1=b/d1;
	b1=abs(b1);
	while(x1<=0)
	 {
	 	x1+=b1;
	 }
	while(x1>b1)
	 {
	 	x1-=b1;
	 }
	return x1;
}
long long nn,m;
long long p[101];
long long mod[101];
long long ans=1;
int main()
{
	freopen("HanXin.in","r",stdin);
	freopen("HanXin.out","w",stdout);
	scanf("%lld%lld",&nn,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld",&p[i],&mod[i]);
		ans*=p[i];
	}
	long long x=0;
	long long ret=0;
	for(int i=1;i<=m;i++)
	{
		if(gcd(ans/p[i],p[i])!=1)
		{
			printf("-1");
			return 0;
		}
		x=((get(ans/p[i],p[i])%ans)*ans/p[i])%ans;
		ret=(ret+(x*mod[i])%ans)%ans;
	}
	long long anss=(nn-ret)%ans;
	if(anss<0) anss=-1;
	printf("%lld",anss);

}