「BZOJ2118」墨墨的等式

2015年7月5日6,5710

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

HINT

对于100%的数据,N≤12,0≤ai≤5*10^5,1≤BMin≤BMax≤10^12。

题解

找一个最小的ai,设其为mn,若x为合法的B,则x+mn也合法
设bi为最小的x,满足\(x~mod~mn~=~i\)
用dijsktra+堆求一下bi,枚举i计算答案贡献

 

 

avatar
  Subscribe  
提醒