记录编号	457633	评测结果	AAAAAAAAAA
题目名称	韩信点兵	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2017-10-09 07:34:48	内存使用	0.32 MiB

#include<cstdio>
#include<iostream>
const int maxn=12;
using namespace std;
inline long long get();
long long exgcd(long long a,long long b,long long &x,long long &y);
long long n,m,x,y;
long long M=1,ans;
long long p[maxn],a[maxn];
int main()
{
	freopen("HanXin.in","r",stdin);
	freopen("HanXin.out","w",stdout);
	n=get(),m=get();
	for(int i=1;i<=m;i++)
	{
		p[i]=get();
		a[i]=get();
		M*=p[i];
	}
	for(int i=1;i<=m;i++)
	{
		int gcd=exgcd(M/p[i],p[i],x,y);
		if(gcd==1)x=(x%p[i]+p[i])%p[i];
		else x=-1;
		ans=(ans+a[i]*(M/p[i])*x)%M;
	}
	if(ans>n)printf("-1");
	else printf("%lld",(n-ans)%M);
	return 0;
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
	if(!b)
	{
		x=1,y=0;
		return a;
	}
	long long r=exgcd(b,a%b,x,y);
	long long t=x;
	x=y,y=t-a/b*y;
	return r;
}
inline long long get()
{
	long long t=0;char c=getchar(),j=1;
	while(!isdigit(c))
		if(c=='-')j=-1,c=getchar();
		else c=getchar();
	while(isdigit(c))
		t=(t<<3)+(t<<1)+c-'0',
		c=getchar();
	return j*t;
}