如题

#include <stdio.h>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
int n, a[20];
long long l, r, d[500005], ans1, ans2;
bool v[500005];
vector<pair<int, int> > G[500005];
priority_queue<pair<long long, int> > q;
int main(void){
	scanf("%d%lld%lld", &n, &l, &r);
	l--;
	int x;
	do{
		scanf("%d", &x);
		n--;
	}while(!x);
	
	for(int i = 1; i <= n; i++)
		scanf("%d", a + i);
	for(int i = 0; i < x; i++)
		for(int j = 1; j <= n; j++)
			G[i].push_back(make_pair((i + a[j]) % x, a[j])), d[i] = 1e13l;
	d[0] = 0;
	q.push(make_pair(0, 0));
	while(q.size()){
		int now = q.top().second;
		q.pop();
		if(v[now])
			continue;
		v[now] = true;
		for(int i = 0; i < G[now].size(); i++){
			int nxt = G[now][i].first;
			int len = G[now][i].second;
			if(d[nxt] > d[now] + len)
				d[nxt] = d[now] + len, q.push(make_pair(-d[nxt], nxt));
		}
	}
	for(int i = 0; i < x; i++){
		if(l >= d[i])
			ans1 += (l - d[i]) / x + 1;
		if(r >= d[i])
			ans2 += (r - d[i]) / x + 1;
	}
	printf("%lld", ans2 - ans1);
	return 0;
}