记录编号	137849	评测结果	AAAAAAAAAA
题目名称	韩信点兵	最终得分	100
用户昵称	Dijkstra	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2014-11-05 12:05:22	内存使用	0.32 MiB

#include<fstream>
#define LL long long
using namespace std;
ifstream fin("HanXin.in");
ofstream fout("HanXin.out");
LL N;
int Q;
LL p[10],a[10],m[10],M=1,t[10];
LL CRT()
{
	for(int i=0;i<Q;i++) m[i]=M/p[i];
	for(int i=0;i<Q;i++)
	{
		for(LL j=1;;j++)
		{
			if(j*m[i]%p[i]==1)
			{
				t[i]=j;
				break;
			}
		}
	}
	LL ans=0;
	for(int i=0;i<Q;i++) ans+=a[i]*m[i]*t[i];
	if(ans%M>N) return -1;
	while(ans>N) ans-=M;
	while(ans<N-M) ans+=M;
	return N-ans;
}
int main()
{
	fin>>N>>Q;
	for(int i=0;i<Q;i++) {fin>>p[i]>>a[i];M*=p[i];}
	fout<<CRT()<<endl;
	return 0;
}