1786. 韩信点兵

            ★★★   输入文件:HanXin.in   输出文件:HanXin.out   简单对比
                  时间限制:1 s   内存限制:256 MB

【题目描述】

韩信是中国军事思想“谋战”派代表人物,被后人奉为“兵仙”、“战神”。“王侯将相”韩信一人全任。“国士无双”、“功高无二,略不世出”是楚汉之时人们对其的评价。作为统帅,他率军出陈仓、定三秦、擒魏、破代、灭赵、降燕、伐齐,直至垓下全歼楚军,无一败绩,天下莫敢与之相争。

相传,韩信带兵打仗时,从不直接清点军队人数。有一次,韩信带1500名兵士打仗,战死四五百人。站3人一排,多出2人;站5人一排,多出4人;站7人一排,多出6人。韩信马上说出人数:1049。

这次,刘邦派韩信带兵N人攻打一座重兵驻扎的城市。城市占领了,可汉军也是伤亡惨重。韩信需要知道汉军至少损失了多少兵力,好向刘邦汇报。

已知韩信发出了M次命令,对于第i次命令,他选择一个素数Pi,要求士兵每Pi人站一排,此时最后一排剩下了ai人。你的任务是帮助韩信求出这种情况下汉军损失兵力的最小值。当然,由于士兵们都很疲惫,他们有可能站错队伍导致韩信得到的数据有误。

【输入格式】

第一行两个正整数N,M,分别代表最初的军队人数和韩信的询问次数。

接下来有M行,每行两个非负整数Pi,ai,代表韩信选择的素数和此时剩下的人数。

输入保证每个素数各不相同。

【输出格式】

输出一行,一个整数。

若有解,输出最小损失人数。若无解,输出-1.

【样例输入】

1500 3
3 2
5 4
7 6

【样例输出】

31

【数据范围】

对于30%的数据,1≤N≤1,000,000,1≤M≤4;

对于50%的数据,1≤N≤100,000,000,1≤M≤8;

对于100%的数据,1≤N≤1,000,000,000,000,1≤M≤10;保证所有素数的乘积≤1012,0≤ai<Pi.

代码:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 20
using namespace std;
;
long long read()
{
    ,f=; char ch=getchar();
    ; ch=getchar();}
    +ch-'; ch=getchar();}
    return x*f;
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
    )
    {
        x=,y=;
        return a;
    }
    long long r=exgcd(b,a%b,x,y),tmp;
    tmp=x,x=y,y=tmp-a/b*y;
    return r;
}
long long crt()
{
    ,sum=;
    ;i<=n;i++)
    {
        long long x,y;
        mi=M/m[i];
        exgcd(mi,m[i],x,y);
        sum=(sum%M+a[i]%M*mi%M*x%M)%M;
    }
    ) sum+=M;
    return sum;
}
int main()
{
    freopen("HanXin.in","r",stdin);
    freopen("HanXin.out","w",stdout);
    s=read(),n=read();
    ;i<=n;i++)
     m[i]=read(),a[i]=read(),M*=m[i];
    tot=crt();
    while(tot+M<=s) tot+=M;
    ans=s-tot;
    if(tot>s) printf("-1");
    else printf("%lld",ans);
}
05-11 12:49