题目
墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。
Input
输入的第一行包含3个正整数，分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数，即数列{an}的值。
Output
输出一个整数，表示有多少b可以使等式存在非负整数解。
Sample Input
3 5
Sample Output
HINT
对于100%的数据，N≤12，0≤ai≤5*10^5，1≤BMin≤BMax≤10^12。
分析
我们先对输入的a进行排序，我们设第一个非零数为a1，我们不难得出如果ka1+b>=BMin,那对于(k+1)a1+b,(k+2)a1+b......(k+m)a1+b同样满足此条件，这里的b就是BMin%a1的余数。所以我们的任务就可以转换为求对于[0,a1-1]的b对应的k的最小值，然后求出在BMax范围内的k的总个数就行了。然后我们考虑建图跑最短路求最小值，设我们有一个余数bi，那通过bi可到达的点就依次(bi+a2)%a1,(bi+a3)%a2......那我们不难得出所到达的点比原来的点多了(bi+aj)/a1个a1，所以这之间的距离就是这个数。既然我们建出了图，那我们就可以最短路求出kmin了，之后经过简单处理就可以求出答案
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const long long inf=1e12+7;
long long vis[1000100],kmin[1000100],a[5000],n,m,bmin,bmax;
priority_queue<pair<long long,long long> >q;
vector<pair<long long,long long> >v[1000100];
inline void read(long long &x){
char s;s=getchar();long long f=1;x=0;while(s>'9'||s<'0'){f=-1;s=getchar();}
while(s<='9'&&s>='0'){x=(x<<3)+(x<<1)+(s-'0');s=getchar();}x*=f;
}
inline void go(int r){
long long i,j,k;
for(i=1;i<r;i++)kmin[i]=inf;
q.push(make_pair(0,0));
while(!q.empty()){
long long x=q.top().second;
q.pop();
if(vis[x])continue;
vis[x]=1;
for(i=0;i<v[x].size();i++){
long long y=v[x][i].first,z=v[x][i].second;
if(kmin[x]+z<kmin[y]){
kmin[y]=kmin[x]+z;
q.push(make_pair(-kmin[y],y));
}
}
}
}
int main(){
long long i,j,k,wh=0,ans=0,x,y;
read(n);read(bmin);read(bmax);
for(i=1;i<=n;i++)
read(a[i]);
sort(a+1,a+n+1);
for(i=1;i<=n;i++)
if(a[i]!=0){
wh=i;
break;
}
if(!wh){puts("0");return 0;}
for(i=wh+1;i<=n;i++)
for(j=0;j<a[wh];j++){
v[j].push_back(make_pair((j+a[i])%a[wh],(j+a[i])/a[wh]));
}
go(a[wh]);
for(i=0;i<a[wh];i++)
if(kmin[i]<inf){
x=(bmax-i)/a[wh];
y=(bmin-i-1)/a[wh]+1;
if(x<kmin[i])continue;
ans+=(x-max(kmin[i],y)+1);
}
cout<<ans<<endl;
return 0;
}