记录编号	144645	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]墨墨的等式	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.740 s
提交时间	2014-12-25 07:58:10	内存使用	4.61 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int SIZE=500010;
const int INF=0x7fffffff/2;
typedef long long LL;
LL Bmin,Bmax;
int N;
int dis[SIZE],A[SIZE];
queue<int> Q;
bool inq[SIZE];
void SPFA(int S){
	for(int i=0;i<SIZE;i++) dis[i]=INF;
	Q.push(S);inq[S]=true;dis[S]=0;
	while(!Q.empty()){
		int x=Q.front();Q.pop();inq[x]=false;
		for(int i=1;i<=N;i++){
			int u=(x+A[i])%A[1],w=(x+A[i])/A[1];
			if(dis[x]+w<dis[u]){
				dis[u]=dis[x]+w;
				if(!inq[u]){
					inq[u]=true;
					Q.push(u);
				}
			}
		}
	}
}
void work(void){
	LL ans=0;
	for(int i=0;i<A[1];i++){
		LL x=max(Bmax/A[1]+(Bmax%A[1]>=i)-dis[i],0LL);
		LL y=max((Bmin-1)/A[1]+((Bmin-1)%A[1]>=i)-dis[i],0LL);
		ans+=x-y;
	}
	printf("%lld\n",ans);
}
void read(void){
	scanf("%d",&N);
	scanf("%lld%lld",&Bmin,&Bmax);
	for(int i=1;i<=N;i++) scanf("%d",&A[i]);
}
int main(){
	freopen("nt2011_equation.in","r",stdin);
	freopen("nt2011_equation.out","w",stdout);
	read();
	SPFA(0);
	work();
	return 0;
}