墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。
Input
输入的第一行包含3个正整数，分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数，即数列{an}的值。
Output
输出一个整数，表示有多少b可以使等式存在非负整数解。
Sample Input
2 5 10
3 5
Sample Output
5
Hint
对于100%的数据，N≤12，0≤ai≤5*10^5，1≤BMin≤BMax≤10^12。
直接说正解，找到a中的一个数(通常找最小的那一个，这样可以降低时间复杂度，至于为什么，看完应该就知道了)，暂且设它为m吧。
我们知道如果存在一个x，它能够被凑出来，那么(x + m), (x + 2m), ...都可以被凑出来。现在我们要找到这么一个最小的x。先建立一些点0,1,2,...,m - 1,表示满足条件的B模m的值。暂时先不考虑如何求出一次Bmin ~ Bmax中满足条件的B，因为可以用0到Bmax中的方案数减去0到Bmin - 1中的方案数。每个点连n - 1条边，第i个点的第j条边连向第(i + a) % m个点，边权为a。
看似有些跑题了，现在来讲讲它在题目中的含义。现在我们希望求到所有满足条件的最小的x，我们知道,当B模m的值为0时，B最小为0。同时我们可以用这个推出与它相邻的点代表的最小的B。再仔细想想，多推一下，这不是等价于求最短路吗？也就是说，从节点0出发，到达i的距离表示，最小的B模m的值为i的B的值。
最后计算一下方案数（相信你会做）就好了。还有特殊处理当某个a等于0的时候，不然会整数被零除，然后无限RE。另外，贡献一发wa，建图注意是单向的，减个a就不知道是不是满足了，笑。
Code
/**
* bzoj
* Problem#2118
* Accepted
* Time:2888ms
* Memory:93712k
*/
#include<iostream>
#include<fstream>
#include<sstream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<ctime>
#include<map>
#include<stack>
#include<set>
#include<queue>
#include<vector>
#ifndef WIN32
#define AUTO "%lld"
#else
#define AUTO "%I64d"
#endif
using namespace std;
typedef bool boolean;
#define inf 0xfffffff
#define smin(a, b) (a) = min((a), (b))
#define smax(a, b) (a) = max((a), (b))
template<typename T>
inline boolean readInteger(T& u) {
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-' && x != -);
if(x == -) {
ungetc(x, stdin);
return false;
}
if(x == '-') {
aFlag = -;
x = getchar();
}
for(u = x - ''; isdigit((x = getchar())); u = u * + x - '');
u *= aFlag;
ungetc(x, stdin);
return true;
} ///map template starts
typedef class Edge{
public:
int end;
int next;
int w;
Edge(const int end = , const int next = , const int w = ):end(end), next(next), w(w) { }
}Edge; typedef class MapManager{
public:
int ce;
int *h;
Edge *edge;
MapManager() { }
MapManager(int points, int limit):ce() {
h = new int[(const int)(points + )];
edge = new Edge[(const int)(limit + )];
memset(h, , sizeof(int) * (points + ));
}
inline void addEdge(int from, int end, int w) {
edge[++ce] = Edge(end, h[from], w);
h[from] = ce;
}
Edge& operator [] (int pos) {
return edge[pos];
}
}MapManager;
#define m_begin(g, i) (g).h[(i)]
///map template ends int n;
long long bmin, bmax;
MapManager g;
int* a;
int moder = inf; inline void init() {
readInteger(n);
readInteger(bmin);
readInteger(bmax);
a = new int[(const int)(n + )];
for(int i = ; i <= n; i++) {
readInteger(a[i]);
if(a[i] == ) {
i--, n--;
continue;
}
smin(moder, a[i]);
}
} boolean *visited;
long long* dis;
queue<int> que;
inline void spfa(int s) {
visited = new boolean[(const int)(moder)];
dis = new long long[(const int)(moder)];
memset(visited, false, sizeof(boolean) * (moder));
memset(dis, 0x7f, sizeof(long long) * (moder));
dis[s] = ;
que.push(s);
while(!que.empty()) {
int e = que.front();
que.pop();
visited[e] = false;
for(int i = m_begin(g, e); i != ; i = g[i].next) {
int &eu = g[i].end;
if(dis[e] + g[i].w < dis[eu]) {
dis[eu] = dis[e] + g[i].w;
if(!visited[eu]) {
que.push(eu);
visited[eu] = true;
}
}
}
}
} inline long long calc(long long x) {
long long ret = ;
for(int i = ; i < moder; i++) {
if(dis[i] <= x)
ret += (x - dis[i]) / (long long)moder + ;
}
return ret;
} inline void solve() {
g = MapManager(moder, moder * n * );
for(int i = ; i < moder; i++) {
for(int j = ; j <= n; j++) {
if(a[j] == moder) continue;
g.addEdge(i, (i + a[j]) % moder, a[j]);
}
}
spfa();
long long res = calc(bmax) - calc(bmin - );
printf(AUTO, res);
} int main() {
init();
solve();
return ;
}