想要写论战捆竹竿，看了题解学了一点姿势，发现了一些奇怪的东西（我以前这道题写的太菜了）
首先这道题可以转化为模 (A_i) 最小值 (m) 意义下的最短路，求出每个模 (m) 意义下的值最少要多少代价可以达成，然后分别计算答案的贡献。这个是经典的同余最短路。
实际上，由于同余，边的更新顺序无关——也就是能分层更新。很像循环下标的背包，但是是取min的而不是方案数。证明的话把交换律和结合律的定义带入即可。
因为顺序无关，考虑单独更新每个权值。因为同余，把 (0 dots m - 1) 的所有点按照模 (A_i mod m) 的值分类，对于点 (i) 能更新到 (j) 当且仅当 (i equiv j (mod A_i))，因此，点被划分成了一堆环，环内的分别处理。
对于一个环，容易证明选择距离最小的点开始更新是最优的。因此从最小点开始，维护一个到当前点最小距离，线性扫过去即可。
复杂度 (O(nm))
所以为什么那么多人都在写最短路啊……为什么我还跑不过最短路啊……
#include <bits/stdc++.h>
typedef long long LL;
const int MAXN = 500010;
int n;
LL bmin, bmax, minn, f[MAXN];
int mn, A[MAXN];
int main() {
std::cin >> n >> bmin >> bmax; --bmin;
mn = 1234567;
for (int i = 1; i <= n; ++i)
std::cin >> A[i], mn = std::min(mn, A[i]);
memset(f, 0x3f, mn << 3);
f[0] = 0;
for (int i = 1; i <= n; ++i) {
int mod = A[i] % mn;
if (!mod) continue;
static bool vis[MAXN];
memset(vis, 0, mn);
for (int j = 0; j < mn; ++j) if (!vis[j]) {
int ma = j, now = j;
while (!vis[now]) {
vis[now] = true;
if (f[now] < f[ma]) ma = now;
now += mod - mn, now += now >> 31 & mn;
}
now = ma;
LL vn = f[now];
do {
f[now] = std::min(f[now], vn);
vn = std::min(vn, f[now]) + A[i];
now += mod - mn, now += now >> 31 & mn;
} while (now != ma);
}
}
LL ans = 0;
for (int i = 0; i < mn; ++i) {
ans += f[i] <= bmax ? (bmax - f[i]) / mn + 1 : 0;
ans -= f[i] <= bmin ? (bmin - f[i]) / mn + 1 : 0;
}
std::cout << ans << std::endl;
return 0;
}