这题我们设$\text{min}a_i=T$, 则我们只需要去考虑用$n$个数能够组成的数对$T$的模的情况。其他可以用$T$累加倍数得到。因为$T$的灵活性最高。
那么设$dis(i)$表示构成的一个数$k$，满足$k \mod T = i$, 且$k$是最小的满足这个条件的数。
那么对于询问$x$能否组成，进行分讨
$dis(i) \leq x$时，可以拼成
而反之则不能。
那么我们求出$dis(i)$的值就能解决这题了。
考虑最短路模型，设$[0,T)$为点，每个点$i$连到$(i + a_j) \mod T$, 边权为$a_j$，最短路一遍即为答案。
对于区间$[\text{Bmin}, \text{Bmax}]$的数，公式求一下即可
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MAXN = 500000 + 5;
LL n, bmin, bmax, a[20], T, dis[MAXN], vis[MAXN];
LL en, hd[MAXN];
struct edge {LL v, w, nxt;} ed[MAXN * 20];
struct data {
LL u, dis;
bool operator < (const data &rhs) const {return dis > rhs.dis;}
};
priority_queue<data > q;
void ins(LL u, LL v, LL w) {ed[++en] = (edge){v, w, hd[u]}, hd[u] = en;}
void clean() {
en = -1, ms(hd, -1), ms(dis, 0x3f), ms(vis, 0);
}
int solve() {
clean();
cin >> n >> bmin >> bmax;
for (LL i = 1; i <= n; ++i) scanf("%lld", &a[i]);
sort(a + 1, a + 1 + n), T = a[1];
for (LL i = 0; i < T; ++i) {
for (LL j = 1; j <= n; ++j) {
ins(i, (i + a[j]) % T, a[j]);
}
}
dis[0] = 0, q.push((data){0, 0});
while (!q.empty()) {
data p = q.top(); q.pop();
if (vis[p.u]) continue ; vis[p.u] = 1;
for (LL i = hd[p.u]; i >= 0; i = ed[i].nxt) {
edge &e = ed[i];
if (dis[e.v] > dis[p.u] + e.w) {
dis[e.v] = dis[p.u] + e.w;
q.push((data){e.v, dis[e.v]});
}
}
}
LL ans = 0;
for (LL i = 0; i < T; ++i) {
if (dis[i] > bmax) continue ;
if (dis[i] < bmin) {
LL t = dis[i] + ((bmin - dis[i]) / T + (bool)((bmin - dis[i]) % T)) * T;
ans += max(0ll, (bmax - t) / T + 1);
} else {
ans += max(0ll, (bmax - dis[i]) / T + 1);
}
}
cout << ans;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
