记录编号	423691	评测结果	AAAAAAAAAA
题目名称	韩信点兵	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-07-12 13:34:46	内存使用	0.00 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long L;
L n;
int m;
L a[11],mod[11];
L M(1),ans(0);
inline void extend_gcd(L a,L b,L &x,L &y){
	if(b==0){
		x=1;
		y=0;
		return;
	}
	extend_gcd(b,a%b,x,y);
	L tmp(x);
	x=y;
	y=tmp-(a/b)*y;
}
inline L CRT(L a[],L m[],int n){
	for(int i=1;i<=n;i++)
		M*=m[i];
	for(int i=1;i<=n;i++){
		L x,y;
		L Mi(M/m[i]);
		extend_gcd(Mi,m[i],x,y);
		ans=(ans+M+Mi*x*a[i])%M;
	}
	//if(ans<0)
	//	ans+=M;
	return ans;
}
inline int gg(){
	freopen("HanXin.in","r",stdin);
	freopen("HanXin.out","w",stdout);
	scanf("%lld%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%lld%lld",&mod[i],&a[i]);
	L ans(CRT(a,mod,m));
	if(ans>n){
		puts("-1");
		return 0;
	}
	while(ans<n)
		ans+=M;
	ans-=M;
	printf("%lld",n-ans);
}
int k(gg());
int main(){;}