luogu 2371墨墨的等式

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

#define DEBUG 0

#define MAXN 15
#define MAXA 500011

typedef long long LL;

typedef pair<int, int> pii;

struct GRAPH {
    vector<vector<pii> > s;

    void ClearEdges() {
        for (auto& i : s) {
            i.resize(0);
        }
    }
    void Init(int n) {
        ClearEdges();
        s.resize(n+1);
    }
    void AddDi(int u, int v, int w) {
        s[u].emplace_back(make_pair(v, w));
    }
};

template <typename T>
void dijkstra(const GRAPH& g, int s, T dist[]) {
    priority_queue<pair<T, int> >q;

    fill(dist, dist + g.s.size(), numeric_limits<T>::max());
    dist[s] = 0;
    q.push(make_pair(0, s));
    while (!q.empty()) {
        s = q.top().second;
        T c = -q.top().first;
        q.pop();
        if (c > dist[s]) continue;//old version
        for (auto i : g.s[s]) {
            int v = i.first;
            c = i.second;
            if (dist[v] > dist[s] + c) {
                dist[v] = dist[s] + c;
                q.push(make_pair(-dist[v], v));
            }
        }
    }
}

int main() {
    static int a[MAXN];
    static LL dist[MAXA];

    int t;
    LL b0, b1;
    cin >> t >> b0 >> b1;
    --b0;
    int n = 0;
    while (t--) {
        int ta;
        cin >> ta;
        if (ta) {
            a[n++] = ta;
        }
    }
    if (n) {
        int mn = a[0];
        for (int i = 1; i < n; ++i) {
            if (a[i]) {
                mn = min(mn, a[i]);
            }
        }
        GRAPH g;
        g.Init(mn);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < mn; ++j) {
                g.AddDi(j, (j + a[i]) % mn, a[i]);
            }
        }
        dijkstra(g, 0, dist);
#if DEBUG
        for (int i = 0; i < mn; ++i) {
            cout << dist[i] << ' ';
        }
        cout << endl;
#endif
        LL ans = 0;
        for (int i = 0; i < mn; ++i) {
            LL up = b1 / mn + 1;    //The included numbers
            if (b1 % mn < i)
                --up;
            LL down = b0 / mn + 1;
            if (b0 % mn < i)
                --down;
            down = max(down, dist[i] / mn);
            if (up >= down) {
                ans += up - down;
            }
        }
        cout << ans << endl;
    } else {
        cout << "0\n";
    }
    return 0;
}