[国家集训队] 墨墨的等式

题目大意

给定 nnaia_iLLRR 求能使等式 a1x1+a2x2+a3x3++anxn=B,  B[L,  R]a_1 x_1 + a_2 x_2 + a_3 x_3 + \cdots + a_n x_n = B, \; B \in [L, \; R] 有非负整数解的 BB 的个数。

1n121 \leqslant n \leqslant 12

0ai500,0000 \leqslant a_i \leqslant 500,000

1LR1×10121 \leqslant L \leqslant R \leqslant 1 \times 10^{12}

题目链接

【国家集训队】墨墨的等式 - Luogu 2371

题解

如果 B=iB = i 是一个合法答案,则 B=i+kajRB' = i + k a_j \leqslant R 也是合法答案。考虑求出最小的 Bi=i  (mod  a1)B_i = i \; (mod \; a_1),其中 a1=min{an}a_1 = min\{a_n\},就可以计算答案了。

对于 BiB_i 的求法,可以转化为最短路。对于一个 i[0,a1)i \in [0, a_1) 和一个 aj  (j1)a_j \; (j \neq 1),建立一条从 ii(i+aj)  mod  a1(i + a_j) \; mod \; a_1、权值为 aja_j 的边,以 00 为起点,ii 的最短距离就是 BiB_i。(十分巧妙的题)

代码

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
64
65
66
67
68
69
70
#include <cstdio>
#include <climits>
#include <queue>
#include <algorithm>
const int MAXN = 15;
const int MAXA = 500005;
struct Edge;
struct Node {
Edge *e;
long long dist;
bool vis;
} N[MAXA];
struct Edge {
Node *u, *v;
Edge *next;
int w;
Edge(Node *u, Node *v, int w) : u(u), v(v), w(w), next(u->e) {}
};
void addEdge(int u, int v, int w) {
N[u].e = new Edge(&N[u], &N[v], w);
}
namespace Dijkstra {
struct HeapNode {
Node *u;
long long dist;
bool operator<(const HeapNode &another) const {
return dist > another.dist;
}
};
void solve(int n) {
for (int i = 0; i < n; i++) N[i].dist = LLONG_MAX, N[i].vis = false;
N[0].dist = 0;
std::priority_queue<HeapNode> q;
q.push((HeapNode) {&N[0], 0});
while (!q.empty()) {
Node *u = q.top().u;
q.pop();
if (u->vis) continue;
u->vis = true;
for (Edge *e = u->e; e; e = e->next) {
if (e->v->dist > u->dist + e->w) {
e->v->dist = u->dist + e->w;
q.push((HeapNode) {e->v, e->v->dist});
}
}
}
}
}
int main() {
int n;
long long L, R;
scanf("%d %lld %lld", &n, &L, &R);
static int a[MAXN];
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
std::sort(a + 1, a + n + 1);
for (int i = 0; i < a[1]; i++) for (int j = 2; j <= n; j++)
addEdge(i, (i + a[j]) % a[1], a[j]);
Dijkstra::solve(a[1]);
long long ans = 0;
for (int i = 0; i < a[1]; i++) {
if (N[i].dist > R) continue;
long long l = std::max((L - N[i].dist) / a[1], 0ll);
if (l * a[1] + N[i].dist < L) l++;
long long r = (R - N[i].dist) / a[1];
if (r * a[1] + N[i].dist > R) r--;
ans += r - l + 1;
}
printf("%lld\n", ans);
return 0;
}