本地笔记整理重发，原文写于 2019/10/28，2019/12/8 上传

题面

题意：求使得关于 \(\{x_i\}\) 的方程 \[ \sum_{i=1}^n a_ix_i = b \] 存在非负整数解的的 \(b \in [l, r]\) 的个数。

数据范围：\(n \le 12, a_i \le 5\times 10^5, l, r \in 10^{12}\)。

神题。不妨设 \(a_1\) 为 \(\{a_i\}\) 当中的最小值。则若对于任意的 \(b \equiv x \pmod{a_1}\) 当中的 \(b\) 如果符合题意有解，那么 \(b+a_1\) 也一定有解。令满足这个性质的最小的 \(b\) 为 \(b_x\)。

考虑在此条件下如何计算解的数目，设 \(m\) 以下满足题意的 \(b\) 有 \(f(m)\) 个，则可以得出计算式： \[ f(m) = \sum_{x=0}^{a_1-1} [b_x \le m]\left(\left\lfloor\frac{m-b_x}{a_1}\right\rfloor+1\right) \] 原理显然。

答案就是 \(f(r) - f(l - 1)\)。

接下来考虑如何求取 \(b_x\)。考虑构建具有 \(a_1\) 个点，编号分别为 \(0,1,2,\cdots,a_1 - 1\) 的图，对于编号 \(u\) 的点，向 \((u + a_i) \bmod a_1, \ (i=2,3,\cdots, n)\) 连边。表示在模 \(a_1\) 意义下，如果 \(u\) 可以有解，那么 \(u+a_i\) 也一定有解。

由于 \(0\) 是一定有平凡解的，我们从 \(0\) 开始跑最短路，就可以求出 \(b_x\)。这背后的思想无疑是非常巧妙的。

复杂度就是 \(\mathcal{O}(na_1(\log n + \log a_1))\)，即为 Dijkstra 的复杂度。

代码

#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
const int N = 13;
const int V = 500010;
const int E = N * V;
const ll INF = 1ll << 60;
ll n, Bl, Br, a[N], mn, len[E];
int fst[V], nxt[E], to[E], tot = 1;
ll dis[V];
void link(int u, int v, ll w) {
    nxt[++tot] = fst[u];
    fst[u] = tot; to[tot] = v; len[tot] = w;
}
void dijkstra() {
    static priority_queue<pli, vector<pli>, greater<pli> > q;
    fill(dis, dis + mn, INF);
    dis[0] = 0; q.push(make_pair(0, 0));
    while (!q.empty()) {
        pli p = q.top(); q.pop();
        int u = p.second;
        if (dis[u] != p.first) continue;
        for (int e = fst[u]; e; e = nxt[e]) {
            int v = to[e];
            if (dis[v] > dis[u] + len[e]) {
                dis[v] = dis[u] + len[e];
                q.push(make_pair(dis[v], v));
            }
        }
    }
}
ll calc(ll x) {
    ll ans = 0;
    for (int i = 0; i < mn; i++)
        if (x >= dis[i]) ans += (x - dis[i]) / mn + 1;
    return ans;
}
int main() {
    scanf("%lld%lld%lld", &n, &Bl, &Br);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    sort(a + 1, a + 1 + n); mn = a[1];
    for (int i = 0; i < mn; i++)
        for (int j = 2; j <= n; j++)
            link(i, (i + a[j]) % mn, a[j]);
    dijkstra();
    printf("%lld\n", calc(Br) - calc(Bl - 1));  
    return 0;
}