题目链接：

数论(×

背包(×

暴搜(×

结论(×

图论(√

惊 不 惊 喜 意 不 意 外

显然，答案可以转化为\(Ans[1,B_{Max}]-Ans[1,B_{Min}-1]\)，现在思考怎么计算\(Ans[1,Lim]\)

首先，若能够组成\(k*a_i+x(0\le x<a_i,k\in\mathbb{N})\)，那么\(l*a_i+x(l>k)\)也可以组成。

若能对每一个\(x\)求出最小的\(k*a_i+x\)，那么就可以轻松地计算有多少\(l\)满足\(l*a_i+x\le Lim\)。

怎么计算？Dijkstra！

建\(0\sim a_i-1\)这\(a_i\)个点，表示对应\(x\)下最小的\(k*a_i+x\)，在剩余系跑一遍最短路即可。

\(a_i\)当然选最小的那个啊~~

时间复杂度 \(O(na_ilog_2(na_i))\)

代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        typedef long long ll;int n,a[15],Mina=1e9;ll BMin,BMax,Dis[500005];struct Rec{    int p;    ll d;    inline bool operator<(const Rec &o)const    {return d>o.d;}};void Dijkstra(){    std::priority_queue
        
          q;    memset(Dis,0x3f,sizeof Dis);    q.push((Rec){0,Dis[0]=0});    while(!q.empty())    {        int x=q.top().p;        ll d=q.top().d;        q.pop();        if(d!=Dis[x])continue;        for(int i=1,y;i<=n;++i)            if(Dis[y=(x+a[i])%Mina]>d+a[i])                q.push((Rec){y,Dis[y]=d+a[i]});    }}ll Query(const ll x){    ll Res=0;    for(int i=0;i