记录编号	527128	评测结果	AAAAAAAAAA
题目名称	韩信点兵	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2019-02-11 17:58:09	内存使用	3.16 MiB

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#define LL long long
using namespace std;
LL ksm(LL x,LL y,LL mod){
	LL re=1;
	while(y){
		if(y&1)re=(re*x)%mod;
		x=(x*x)%mod;
		y>>=1;
	}
	return re;
}
LL n,m,a[11],p[11],M=(LL)1,ans=0,N=(LL)1;
int main(){
	freopen("HanXin.in","r",stdin);
	freopen("HanXin.out","w",stdout);
	scanf("%lld%lld",&m,&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&p[i],&a[i]);
		M*=p[i];N*=(p[i]-(LL)1);
	}
	for(int i=1;i<=n;i++)ans=(M+ans+a[i]*M/p[i]%M*ksm(M/p[i],p[i]-2,p[i])%M)%M;
	if(ans>=m)printf("-1");
	else printf("%lld",(m-ans)%M);
	return 0;
}