「BZOJ2118」墨墨的等式

Description

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

Input

输入的第一行包含33个正整数,分别表示NNBMinB_{Min}BMaxB_{Max}分别表示数列的长度、BB的下界、BB的上界。输入的第二行包含NN个整数,即数列{an}\{a_n\}的值。

Output

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

Sample Input

1
2
2 5 10
3 5

Sample Output

1
5

HINT

对于20%20\%的数据,N5N \le 51BMinBMax101 \le B_{Min} \le B_{Max} \le 10
对于40%40\%的数据,N10N \le 101BMinBMax1061 \le B_{Min} \le B_{Max} \le 10^6
对于100%100\%的数据,N12N \le 120ai5×1050 \le a_i \le 5\times 10^51BMinBMax10121 \le B_{Min} \le B_{Max} \le 10^{12}

Solution

aa数组从小到大排序,去掉ai=0a_i=0
一个合法的BB,一定可以写作a1+ta_1+t的情况。
那么对于所有能到达的x(moda1)x\pmod{a_1},找到00到其的最小tt,显然对于t+a1,t+2a1,t+ka1t+a_1,t+2a_1,\cdots t+ka_1它都能到达,能到达的数就是Bdia1+1\frac{B-d_i}{a_1}+1,直接枚举xx也就是余数直接求。答案就是f(r)f(l1)f(r)-f(l-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 15;

int n;
ll mn, mx;
int a[N];
ll d[510000];
priority_queue<pii,vector<pii>,greater<pii> > q;
void dijkstra() {
for(int i = 0; i <= 5e5; ++i) d[i] = 1e18;
d[0] = 0;
q.push(mk(0, 0));
while(!q.empty()){
pii now = q.top(); q.pop();
int x = now.nd;
for(int i = 1; i <= n; ++i) {
int y = (x + a[i]) % a[1];
if(d[y] > d[x] + a[i]) {
d[y] = d[x] + a[i];
q.push(mk(d[y], y));
}
}
}
}

ll solve(ll x) {
ll ans = 0;
for(int i = 0; i < a[1]; ++i) if(x >= d[i])
ans += (x - d[i]) / a[1] + 1;
return ans;
}

int main() {
n = read(), mn = read(), mx = read();
for(int i = 1; i <= n; ++i) {
a[i] = read();
if(!a[i]) --i,--n;
}
sort(a + 1, a +1 + n);

dijkstra();
writeln(solve(mx) - solve(mn - 1));
return 0;
}