Luogu

分析

同余类最短路。

设 $a$ 中的最小值为 $k$ 。容易发现，如果能表示出 $xk+t\;(0\leq t<k)$ ，那么也能表示出 $(x+1)k+t$ 。

把 $t$ 看做余数，然后对于每个 $a_i$ ，从 $t$ 向 $(t+a_i) \bmod k$ 连一条边权为 $a_i$ 的边。

然后跑 SPFA 求出最短路，再对每个余数统计答案即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=12+10;
const int M=500000+10;

int n,l,r,k;
int a[N];
int dis[M],inq[M];

inline void spfa() {
    memset(dis,0x3f,sizeof(dis)); dis[0]=0;
    queue<int> Q; Q.push(0);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (re int i=1;i<=n;++i) {
            int v=(u+a[i])%k;
            if (dis[u]+a[i]<dis[v]) {
                dis[v]=dis[u]+a[i];
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
}

signed main() {
    n=read(),l=read(),r=read(); k=1e18;
    for (re int i=1;i<=n;++i) a[i]=read(),k=min(k,a[i]);
    spfa(); int ans=0;
    for (re int i=0;i<k;++i) {
        if (dis[i]<=r) ans+=(r-dis[i])/k+1;
        if (dis[i]<l) ans-=(l-1-dis[i])/k+1;
    }
    printf("%lld\n",ans);
    return 0;
}