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

题目大意

给定 $n$、$a_i$、$L$、$R$ 求能使等式 $a_1 x_1 + a_2 x_2 + a_3 x_3 + \cdots + a_n x_n = B, \; B \in [L, \; R]$ 有非负整数解的 $B$ 的个数。

$1 \leqslant n \leqslant 12$

$0 \leqslant a_i \leqslant 500,000$

$1 \leqslant L \leqslant R \leqslant 1 \times 10^{12}$

题目链接

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

题解

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

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

代码

#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;
}