困到死亡，从问大佬题到AC都仿佛活在梦中。
大佬建边考虑了很多，但N很小这里就直接暴力建了。
考虑找出最小的a，把bmin~bmax这段区间按mod a分成若干份，若是最小的B≡x（mod a）可以构造出，则比它大的在区间中的B≡x（mod a）都可以构造出。
如何找最小的B，当一个数可以构造出，它加a[i]也可以构造出。
于是把a数组排序，建0~a[1]-1共a[1]个点，然后枚举a[1]之后的每个a[i]，从每个点x向(x+a[i])%a[1]连边长为a[i]的边，然后跑最短路。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
typedef long long LL;
using namespace std;
const int maxn=6e6+299;
int n,a[20],ecnt,fir[maxn],nxt[maxn],to[maxn],vis[maxn];
LL ans,MIN,MAX,dis[maxn],val[maxn];
void add(int u,int v,LL w) {
nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w;
}
queue<int>que;
void spfa() {
memset(dis,127,sizeof(dis));
memset(vis,0,sizeof(vis));
que.push(0);
vis[0]=1; dis[0]=0;
while(!que.empty()) {
int x=que.front();
que.pop(); vis[x]=0;
for(int i=fir[x];i;i=nxt[i]) {
if(dis[to[i]]>dis[x]+val[i]) {
dis[to[i]]=dis[x]+val[i];
if(!vis[to[i]]) {
vis[to[i]]=1;
que.push(to[i]);
}
}
}
}
}
int main()
{
scanf("%d%lld%lld",&n,&MIN,&MAX);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=2;i<=n;i++)
for(int j=0;j<a[1];j++)
add(j,(j+a[i])%a[1],a[i]);
spfa();
for(int i=0;i<a[1];i++) if(dis[i]<=MAX){
LL l=max(MIN-1,dis[i]-1),ll=l/a[1];
if(l%a[1]>=i) ll++;
LL rr=MAX/a[1]; if(MAX%a[1]>=i) rr++;
ans+=rr-ll;
}
printf("%lld
",ans);
return 0;
}
不知道自己在说什么，我仿佛活在梦中。