Description
墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。
Input
输入的第一行包含3个正整数，分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数，即数列{an}的值。
Output
输出一个整数，表示有多少b可以使等式存在非负整数解。
Sample Input
2 5 10
3 5
3 5
Sample Output
5
HINT
对于100%的数据，N≤12，0≤ai≤5*10^5，1≤BMin≤BMax≤10^12。
最短路。
终于会用堆优化的dijkstra了，STL中的priority_queue默认的是大根堆，为此debug两小时，然后重新看别人博客学了一下才知道人家是默认大根堆。。
找出a1到an中的最小值p，则如果可以构造出答案x，就可以构造出答案x+p
对于每个余数x（mod p），计算出最小的可以被构造出来的余数为x的数
根据余数建点，根据a[i]的值加边。
加边部分代码+注释：
for(int i=1;i<=n;++i) {
a[i]=read();
if(a[i]>bmax||!a[i]) i--,n--;//0或大于bmax的a[i]是没有用的
}
sort(a+1,a+n+1);
n=unique(a+1,a+n+1)-(a+1);//排序、去重
ll x;p=a[1];f[0]=1;//f为bool数组，f[x]=1表示余数为x的最小a[i]已经用于加边了
if(p==1) {
printf("%lld",bmax-bmin+(ll)1);
return 0;
}
for(int i=2;i<=n;++i) {
x=a[i]%p;
if(f[x]) continue;//有更小的j（a[j]<a[i]）使得a[j]≡a[i]，不需要再用a[i]去加边
f[x]=1;
for(int j=0;j<p;++j) add(j,(j+x)%p,a[i]);
}
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
#define ll long long
const int maxn=15,maxs=5e5+10,maxm=maxn*maxs;
ll n,p;
ll a[maxn],bmin,bmax,ans=0;
bool f[maxs];
ll aa;char cc;
ll read() {
aa=0;cc=getchar();
while(cc<'0'||cc>'9') cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
return aa;
}
int fir[maxs],nxt[maxm],to[maxm],e=0;ll v[maxm];
void add(int x,int y,ll z) {
to[++e]=y;nxt[e]=fir[x];fir[x]=e;v[e]=z;
}
struct pq{
ll x,d;
bool operator <(const pq& a) const{return d>a.d;}
};
priority_queue<pq> Q;
ll dis[maxs];
bool vis[maxs];
void dijkstra() {
memset(dis,0x3f3f3f3f,sizeof(dis));
dis[0]=0;
ll x,y,z;
Q.push((pq){0,0});
while(!Q.empty()) {
x=Q.top().x;Q.pop();
if(vis[x]) continue;
vis[x]=1;
for(y=fir[x];y;y=nxt[y]) {
z=to[y];
if(dis[z]<=dis[x]+v[y]) continue;
dis[z]=dis[x]+v[y];
Q.push((pq){z,dis[z]});
}
}
}
ll get_ans(ll l,ll r,ll x) {
return (r-l)/p+1;
}
int main() {
n=read();bmin=read();bmax=read();
for(int i=1;i<=n;++i) {
a[i]=read();
if(a[i]>bmax||!a[i]) i--,n--;
}
sort(a+1,a+n+1);
n=unique(a+1,a+n+1)-(a+1);
ll x;p=a[1];f[0]=1;
if(p==1) {
printf("%lld",bmax-bmin+(ll)1);
return 0;
}
for(int i=2;i<=n;++i) {
x=a[i]%p;
if(f[x]) continue;
f[x]=1;
for(int j=0;j<p;++j) add(j,(j+x)%p,a[i]);
}
dijkstra();
for(ll i=bmin;i<min(bmin+p,bmax+1);++i) {
x=i%p;
if(dis[x]>bmax) continue;
ans+=get_ans(max(i,dis[x]),bmax,x);
}
cout<<ans;
return 0;
}
给出对拍的rand：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<ctime>
using namespace std;
#define ll long long
const int n=10;
ll bmin,bmax;
int main() {
srand((unsigned)time(NULL));
cout<<n<<" ";
bmin=((rand()%5)*(rand()%(int)2e3)*1e3+rand()%(int)1e4)*1e4+rand()%(int)1e4;
bmax=bmin+rand();
cout<<bmin<<" "<<bmax<<"
";
ll x;
for(int i=1;i<=n;++i) {
x=rand()%1000+(rand()%50)*3e3*(rand()%3);
cout<<x<<" ";
}
cout<<"
";
return 0;
}