Description

墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。

Input

输入的第一行包含3个正整数，分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数，即数列{an}的值。

Output

输出一个整数，表示有多少b可以使等式存在非负整数解。

Sample Input

2 5 10

3 5

Sample Output

5

解题思路：

详见

其实就是成了n元

用其他n-1元在第n元模环境下最短路。

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 typedef long long lnt; 6 struct pnt{ 7     int hd; 8     int no; 9     lnt dis;10     bool vis;11     bool friend operator < (pnt x,pnt y)12     {13         return x.dis>y.dis;14     }15 }p[1000000];16 struct ent{17     int twd;18     int lst;19     lnt vls;20 }e[10000000];21 lnt a[1000000];22 int n,m;23 int cnt;24 lnt Bmin,Bmax;25 lnt ans;26 std::priority_queue
         
          Q;27 void ade(int f,int t,lnt v)28 {29     cnt++;30     e[cnt].twd=t;31     e[cnt].lst=p[f].hd;32     e[cnt].vls=v;33     p[f].hd=cnt;34     return ;35 }36 void Dij(void)37 {38     for(int i=0;i
          
           p[x].dis+e[i].vls)56 {57 p[to].dis=p[x].dis+e[i].vls;58 Q.push(p[to]);59 }60 }61 }62 return ;63 }64 int main()65 {66 scanf("%d%lld%lld",&n,&Bmin,&Bmax);67 if(n==0)68 {69 printf("0\n");70 return 0;71 }72 for(int i=1;i<=n;i++)73 {74 scanf("%lld",&a[i]);75 if(a[i]==0)76 {77 n--;78 i--;79 }80 }81 for(int i=2;i<=n;i++)82 for(int j=0;j
           
            Bmax)88 continue;89 ans+=(Bmax-p[i].dis)/a[1]+1;90 if(p[i].dis