题解 P2371 【[国家集训队]墨墨的等式】
同余最短路
题意分析： 给你一个n，有n个数，分别为a1，a2.....an，然后存在一个等式 a1x1+a2x2+.....+anxn=B 其中x都是非负整数，此时这些x叫做一组解，给你B的一个上下届，然后问：对于这个上下界，一共有多少组解
思路： 首先我们需要简化问题，(这应该是我们都擅长的)，由于a有很多，就很烦，我们不妨找到最小的那个a（amin），然后对于一个数aixi(1<=i<=n)，我们都可以将其化成amin的其中一个类，我们一共会得到amin个类(这是显然的)0,1.....amin-1
实现： 我们想要找到上下界[l,r]中有几个数我们可以用a1x1+a2x2+.....+anxn来表示，我们不妨对答案分类，没错，分成amin类，显然，对于x类，表示答案%amin等于x，那么我们就可以用amin来表示所有的答案了
来性感的看一下：
我们用dis[x]表示x类的最小值(对于此题，显然，0类的最小值是0,此时所有的x都等于0，我们的答案为0，所以0类答案的最小值为0)(对，没错，只是对于此题，还有不太一样的，比如P3403，这个题比这道题要简单一些，大家可以搞完这个墨墨然后去做那个题，当做练习)
我们所有的答案：
dis[0],dis[0]+amin,dis[0]+amin+amin,dis[0]+amin+amin+amin
dis[1],dis[1]+amin,dis[1]+amin+amin,dis[1]+amin+amin+amin
........
dis[amin-1]。。。。。。。。。。。。
那好，我们最后用最短路spfa来最求dis就好了，由于边有点多，我就没有建边，spfa我就不去解释了，如果大家看懂了那个spfa，相信大家对spfa，还有对同余最短路都会有更得理解了，自然的，这道题也就做出来了
上代码：
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <queue>
# include <stack>
# define FOR(i,st,ed) for(int i=st;i<=ed;++i)
# define _FOR(u) for(int v,i=hd[u];i;i=e[i].nt)
# define _V v=e[i].to
# define int long long
using namespace std;
int re(){
int s=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){s=(s<<1)+(s<<3)+ch-'0';ch=getchar();}
return s*f;
}
const int N=5e5+7;
const int inf=1e15;
int n,l,r;int ans;
int a[N];
int dis[N],vis[N];
queue <int> q;
void spfa(){
FOR(i,0,a[1]-1) dis[i]=inf;
dis[0]=0;q.push(0);vis[0]=1;
while(q.size()){
int u=q.front();q.pop();vis[u]=0;
FOR(i,2,n){
int v=(u+a[i])%a[1];
if(dis[v]>dis[u]+a[i]){
dis[v]=dis[u]+a[i];
if(!vis[v]) q.push(v),vis[v]=1;
}
}
}
}
signed main(){
n=re();l=re();r=re();
FOR(i,1,n) a[i]=re();
sort(a+1,a+n+1);
spfa();
FOR(i,0,a[1]-1){
if(dis[i]<l) ans+=(r-dis[i])/a[1]+1-(l-1-dis[i])/a[1]-1;
//差分时，注意是l-1，而不是l
if(l<=dis[i]&&dis[i]<=r) ans+=(r-dis[i])/a[1]+1;
}
cout<<ans;
return 0;
}