记录编号	423746	评测结果	AAAAAAAAAA
题目名称	韩信点兵	最终得分	100
用户昵称	yymxw	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2017-07-12 15:22:35	内存使用	0.31 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
long long n,m,shu=1;
long long w[20],b[20];
long long gcd(long long a,long long b,long long &x,long long &y)
{
  long long ret,tmp;
  if(!b)
  {
    x=1;
    y=0;
    return a;
  }
  ret=gcd(b,a%b,x,y);
  tmp=x;
  x=y;
  y=tmp-a/b*y;
  return ret;
}
long long china(long long w[],long long b[],long long k)
{
  long long x,y,a=0,m;
  for(int i=1;i<=k;++i)
    shu*=w[i];
  for(int i=1;i<=k;++i)
  {
    m=shu/w[i];
    long long s=gcd(w[i],m,x,y);
    //cout<<s<<endl;
    a=(a+y*m*b[i])%shu;
  }
  if(a>0)
    return a;
  else 
    return a+shu;
}
int main()
{
  freopen("HanXin.in","r",stdin);
  freopen("HanXin.out","w",stdout);
  cin>>n>>m;
  for(int i=1;i<=m;++i)
    cin>>w[i]>>b[i];
  long long ji=china(w,b,m),ans;
  //cout<<ji<<endl;
  while(1)
  {
    if(ji+shu>n)
      break;
    ji+=shu;
  }
  if(n-ji<0)
    ans=-1;
  else
    ans=n-ji;
  cout<<ans;
  //system("pause");
  return 0;
}