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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
void extend_gcd(LL a,LL b,LL &x,LL &y,LL &d){
	if(!b){x=1,y=0,d=a;}
	else{extend_gcd(b,a%b,y,x,d),y-=(a/b)*x;}
}
LL M;//所有模的乘积
LL China(LL a[],LL m[],LL n){//模m[i]余a[i],i从1到n
	LL ans=0,d,x,y,w;
	for(int i=1;i<=n;i++){
		w=M/m[i];
		extend_gcd(w,m[i],x,y,d);
		ans+=w*x*a[i];
		ans%=M;
	}
	if(ans<0) ans+=M;
	return ans;
}
LL mx,n;//最初人数mx,询问次数n
LL a[20],p[20];
void work(void){
	LL x=China(a,p,n);
	if(x>mx){
		cout<<-1<<endl;
	}
	else{
		cout<<(mx-x)%M<<endl;
	}
}
void read(void){
	cin>>mx>>n;
	M=1;
	for(int i=1;i<=n;i++){
		cin>>p[i]>>a[i];
		M*=p[i];
	}
}
int main(){
	freopen("HanXin.in","r",stdin);
	freopen("HanXin.out","w",stdout);
	read();
	work();
	return 0;
}