同余最短路
一堆点凑成了 $\mathrm{sum}$, 则 $\mathrm{sum}$ 可以表示成 $\mathrm{k \times a[1] + i}$ 的形式.
即 $\mathrm{k}$ 为商，后面的 $\mathrm{i}$ 为 $\mathrm{mod}$ $\mathrm{a[1]}$ 的余数.
令 $\mathrm{dis[i]}$ 表示 $\mathrm{sum}$ 模 $\mathrm{a[1]}$ 等于 $\mathrm{i}$ 的情况下 $\mathrm{sum}$ 的最小值.
通过 $\mathrm{dis[i]}$ 可以得到商，也就是 $\mathrm{k}$ 的最小值.
通过 $\mathrm{k_{min}}$，可得到所有 $\mathrm{k‘ \times a[1]+i}$, $\mathrm{k_{min} \leqslant k‘}$.
由于后面的余数 $\mathrm{i}$ 不同，所以不重不漏统计到 $\mathrm{sum}$ 的所有可能取值.
墨墨的等式
来源：洛谷P2371 [国家集训队]墨墨的等式
同余最短路的模板题，统计 $[l,r]$ 区间内的答案时直接 $\mathrm{calc(r)-calc(l-1)}$ 即可.
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 500009
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const ll inf=(ll)1e12;
queue<int>q;
int a[12],inq[N];
ll dis[N];
int main() {
// setIO("input");
int n ;
ll L, R;
scanf("%d%lld%lld",&n,&L,&R);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
sort(a+1,a+1+n);
int mx=a[1];
for(int i=0;i<mx;++i) dis[i]=inf;
dis[0]=0;
inq[0]=1;
q.push(0);
while(!q.empty()) {
int u=q.front(); q.pop();
inq[u]=0;
for(int i=1;i<=n;++i) {
int v = (u + a[i]) % mx;
if(dis[v] > dis[u] + a[i]) {
dis[v] = dis[u] + a[i];
if(!inq[v]) {
q.push(v);
inq[v] = 1;
}
}
}
}
for(int i=0;i<mx;++i) {
if(dis[i] == inf) continue;
dis[i] -= i;
dis[i] /= mx;
}
ll ans=0;
for(int i=0;i<mx;++i) {
ll pl = (L - 1 - i) / mx;
ll pr = (R - i) / mx;
ll t1 = max(0ll, pl - dis[i] + 1);
ll t2 = max(0ll, pr - dis[i] + 1);
ans += t2 - t1;
}
printf("%lld\n", ans);
return 0;
}