「国家集训队」墨墨的等式

题目大意：求有多少个 $b \in [l,r]$ 使得方程 $\sum\limits_{i=1}^{n}a_ix_i=b$ 有非负整数解。$n \leq 20, 1 \leq l \leq r \leq 10^{12}$

如果 $x_i$ 可以为负的话，$b$ 的取值就是 $\gcd(a_i)$ 的所有倍数。

PoPoQQQ的题解

对于所有能拼出来的 $k \times a_i + x$，$dis[x]$ 表示最小的 $k$ 是多少。

#include <cstdio>
#include <cstring>
#include <queue>

typedef long long LL;
const int N = 500005;
struct Pair {
    int x, y;
    bool operator < (const Pair &rhs) const {
        return x > rhs.x;
    }
};
int n = 1e9, m, a[25], vis[N], dis[N];
std::priority_queue<Pair> Q;

void dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    dis[0] = 0, Q.push((Pair){0, 0});
    int cnt = 0;
    while (!Q.empty()) {
        int u = Q.top().y; Q.pop();
        if (vis[u]) continue;
        if (++cnt == n) return;
        vis[u] = 1;
        for (int i = 1; i <= m; ++i) {
            int v = (u + a[i]) % n, x = (u + a[i] % n >= n);
            if (dis[v] > dis[u] + a[i] / n + x)
                dis[v] = dis[u] + a[i] / n + x, Q.push((Pair){dis[v], v});
        }
    }
}

int main() {
    LL l, r, ans = 0;
    scanf("%d%lld%lld", &m, &l, &r);
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &a[i]);
        if (!a[i]) { --i, --m; continue; }
        if (a[i] < n) n = a[i];
    }
    if (!m) { puts("0"); return 0; }
    dijkstra();
    for (int i = 0; i < n; ++i) {
        LL x = 1LL * dis[i] * n + i;
        if (x < l) x += (l - x + n - 1) / n * n;
        if (x <= r) ans += (r - x) / n + 1;
    }
    printf("%lld\n", ans);
    return 0;
}