「BZOJ」墨墨的等式 - 同余最短路

题面

Description

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

Input

输入的第一行包含 3 个正整数,分别表示 N B_{\text{Min}} B_{\text{Max}} 分别表示数列的长度、 B 的下界、 B 的上界。

输入的第二行包含 N 个整数,即数列 \{a_n\} 的值。

Output

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

Sample Input

1
2
2 5 10
3 5

Sample Output

1
5

HINT

对于 100\% 的数据, N\leq 12,0\leq a_i\leq 5\times 10^5, 1\leq B_{\text{Min}}\leq B_\text{Max}≤10^{12}

Source

题解

同余最短路板子题

记录最小值然后继续像上一篇Blog中写到的方式算即可

代码:

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
#include <bits/stdc++.h>

#define int long long

const int N = 500000 + 10;

int n, mod = LLONG_MAX;
int f[N];
int d[N];
int v[N];

void dij () {
std::queue <int> q;
for (int i = 0; i <= mod; i++) d[i] = LLONG_MAX;
q.push(0);
d[0] = 0, v[0] = 1;
while (!q.empty()) {
int from = q.front(); q.pop();
for (int i = 1; i <= n; i++) {
int to = (from + f[i]) % mod, dist = f[i];
if (d[to] > d[from] + dist) {
d[to] = d[from] + dist;
if (!v[to]) q.push(to);
v[to] = 1;
}
}
}
}

inline int calc (int x) {
int ret = 0;
for (int i = 0; i < mod; i++) {
// printf("d[%d] = %d\n", i, d[i]);
if (d[i] <= x) ret += (x - d[i]) / mod + 1;
}
return ret;
}

signed main () {
int l, r;
scanf("%lld%lld%lld", &n, &l, &r);
for (int i = 1; i <= n; i++) scanf("%lld", f + i), mod = std::min(mod, f[i]);
dij();
printf("%lld\n", calc(r) - calc(l - 1));
}
坚持原创技术分享,您的支持将鼓励我继续创作!