记录编号	420391	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]墨墨的等式	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.713 s
提交时间	2017-07-04 17:33:24	内存使用	6.50 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5e5+10;
ll l,r;
int n,m,a[20],dis[N];
struct Queue{
	struct node{
		int k;
		node *next;
		node(int key){k=key;next=0;}
	}*head,*x;
	void push(int k){
		x=new node(k);
		x->next=head;
		head=x; 
	}
	void pop(){
		x=head;
		head=head->next;
		delete x;
	}
	int front(){
		return head->k;
	}
	bool empty(){
		return !head;
	}
}Q[N];
bool vis[N];
int main()
{
	freopen("nt2011_equation.in","r",stdin);
	freopen("nt2011_equation.out","w",stdout);
	scanf("%d%lld%lld",&n,&l,&r);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	m=a[n];
	dis[0]=0;Q[0].push(0);
	for (int i=1;i<m;i++) dis[i]=1e9;
	for (int i=0;i<=m;i++)
	while (!Q[i].empty()){
		int v=Q[i].front();Q[i].pop();
		if (vis[v]) continue;
		vis[v]=1;
		for (int i=1;i<n;i++){
			int l=0,p=v+a[i];
			if (p>=m) p-=m,l=1;
			if (dis[p]>dis[v]+l){
				dis[p]=dis[v]+l;
				Q[dis[p]].push(p);
			} 
		}
	}
	ll ans=0;
	for (int i=0;i<m;i++)
	if (dis[i]<1e9){
		ans+=max((r-i+m)/m-dis[i],0ll);
		ans-=max((l-i-1+m)/m-dis[i],0ll);
	}
	printf("%lld\n",ans);
	return 0;
}