记录编号	370331	评测结果	AAAAAAAAAA
题目名称	韩信点兵	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2017-02-13 15:13:01	内存使用	0.29 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=15;
long long qpow(long long,long long,long long);
long long k,m[maxn],a[maxn],M=1,ans=0;
int n;
int main(){
	freopen("HanXin.in","r",stdin);
	freopen("HanXin.out","w",stdout);
	scanf("%lld%d",&k,&n);
	for(int i=0;i<n;i++){
		scanf("%lld%lld",&m[i],&a[i]);
		M*=m[i];
	}
	for(int i=0;i<n;i++){
		long long Mi=M/m[i];
		ans=(ans+a[i]*Mi%M*qpow(Mi,m[i]-2,m[i])%M)%M;
	}
	if(ans>k)printf("-1");
	else printf("%lld",(k-ans)%M);
	return 0;
}
long long qpow(long long a,long long b,long long p){
	long long ans=1;
	for(;b;b>>=1,a=a*a%p)if(b&1)ans=ans*a%p;
	return ans;
}