记录编号	159746	评测结果	AAAAAAAAAA
题目名称	韩信点兵	最终得分	100
用户昵称	清羽	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2015-04-22 16:37:58	内存使用	0.32 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<ctime>
#include<algorithm>
using namespace std;

typedef long long LL;

const int maxn=10;

char buf[40];
LL p[maxn],a[maxn],n,N,M=1;

template<class T> inline bool getd(T& x)
{
	int ch=getchar();
	bool neg=false;
	while(ch!=EOF && ch!='-' && !isdigit(ch)) ch=getchar();
	if(ch==EOF) return false;
	if(ch=='-'){
		neg=true;
		ch=getchar();
	}
	x=ch-'0';
	while(isdigit(ch=getchar())) x=x*10+ch-'0';
	if(neg) x=-x;
	return true;
}

template<class M> void putd(M x)
{
	int p=0;
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x==0) buf[p++]=0;
	while(x){
		buf[p++]=x%10;
		x/=10;
	}
	for(int i=p-1;i>=0;i--) putchar(buf[i]+'0');
	putchar('\n');
}

void gcd(LL a,LL b,LL& d,LL& x,LL& y)
{
	if(!b){ x=1;y=0;d=a; }
	else{ gcd(b,a%b,d,y,x);y-=x*(a/b); }
}

LL inv(LL a,LL m) //求a在模m下的逆元
{
	LL x,y,d;
	gcd(a,m,d,x,y);
	return (d!=1)?-1:(x+m)%m;
}

void init()
{
	getd(N);getd(n);
	for(int i=0;i<n;i++){
		getd(p[i]);
		getd(a[i]);
		M*=p[i];
	}
}

void work()
{
	LL ans=0;
	for(int i=0;i<n;i++){
		LL x=inv(M/p[i],p[i]);
		if(x==-1){
			putd(-1);
			return;
		}
		ans=(ans+M/p[i]*x*a[i])%M;
	}
	if(ans>N){
		putd(-1);
		return;
	}
	while(ans+M<=N) ans+=M;
	putd(N-ans);
}

int main()
{
	freopen("HanXin.in","r",stdin);
	freopen("HanXin.out","w",stdout);
	init();
	work();
	fclose(stdin);
	fclose(stdout);
	return 0;
}