记录编号	144603	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]墨墨的等式	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	1.020 s
提交时间	2014-12-24 15:04:37	内存使用	34.65 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define Maxn 4000010
using namespace std;
int n;
long long BMin,BMax,ans=0;
int dis[Maxn],a[Maxn];
queue<int> q;
bool vis[Maxn]={0};
void spfa(int s){
    memset(dis,0x3f,sizeof(dis));
    vis[s]=true; dis[0]=0;
    q.push(s);
    while(!q.empty()){
        int now=q.front(); q.pop();
        vis[now]=false;
        for(int i=1;i<=n;i++){
            int p=(now+a[i])%a[1],len=(now+a[i])/a[1];
            if(dis[p]>dis[now]+len){
                dis[p]=dis[now]+len;
                if(!vis[p]){
                    vis[p]=true;
                    q.push(p);
                }
            }
        }
    }
    for(int i=0;i<a[1];i++){
        long long x=max(BMax/a[1]+(BMax%a[1]>=i)-dis[i],0LL);
        long long y=max((BMin-1)/a[1]+((BMin-1)%a[1]>=i)-dis[i],0LL);
        ans+=x-y;
    }
}
int main(){
	freopen("nt2011_equation.in","r",stdin);
	freopen("nt2011_equation.out","w",stdout);
    scanf("%d%lld%lld",&n,&BMin,&BMax);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    spfa(0);
    printf("%lld\n",ans);
    return 0;
}