Given four positive integers (x, y, z, H), the goal is to count the number of integers (d) in the range ([0, H]) that can be expressed as (d = a x + b y + c z), where (a, b, c) are non-negative integers.

If a value (k) can be written as (k = b y + c z) with non-negative (b) and (c), then (k) is a valid solution. Additionally, all numbers (k + x, k + 2x, k + 3x, \dots) up to (H) are also valid solutions.

Define a function (g(i)) as the minimum value of (b y + c z) such that ((b y + c z) \mod x = i).

Key observations:

• (g(i) + y \ge g((i + y) \mod x))
• (g(i) + z \ge g((i + z) \mod x))

These inequalities resemble constraints in graph theory, allowing the problem to be modeled as a shortest path problem. Construct a directed graph with nodes (0, 1, \dots, x-1):

• For each (i), add an edge from (i) to ((i + y) \mod x) with weight (y).
• For each (i), add an edge from (i) to ((i + z) \mod x) with weight (z).

Compute the shortest distances (dist[i]) from node (0) using Dijkstra's algorithm or SPFA. Then, the total number of valid (d) values is:

[\sum_{i=0}^{x-1} \left( \left\lfloor \frac{H - dist[i]}{x} \right\rfloor + 1 \right)]

The (+1) accuonts for (dist[i]) itself being a solution. For the specific problem, decrement (H) by 1 before applying this formula.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

int main() {
    ll H, x_val, y_val, z_val;
    cin >> H >> x_val >> y_val >> z_val;
    H--;
    vector<ll> distance(x_val, INF);
    vector<bool> visited(x_val, false);
    vector<vector<pair<ll, ll>>> graph(x_val);
    for (int i = 0; i < x_val; i++) {
        graph[i].emplace_back((i + y_val) % x_val, y_val);
        graph[i].emplace_back((i + z_val) % x_val, z_val);
    }
    distance[0] = 0;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> pq;
    pq.emplace(0, 0);
    while (!pq.empty()) {
        ll current = pq.top().second;
        pq.pop();
        if (visited[current]) continue;
        visited[current] = true;
        for (auto &edge : graph[current]) {
            ll neighbor = edge.first;
            ll weight = edge.second;
            if (distance[neighbor] > distance[current] + weight) {
                distance[neighbor] = distance[current] + weight;
                pq.emplace(distance[neighbor], neighbor);
            }
        }
    }
    ll result = 0;
    for (int i = 0; i < x_val; i++) {
        if (H >= distance[i]) {
            result += (H - distance[i]) / x_val + 1;
        }
    }
    cout << result << endl;
    return 0;
}

This approach extends to problems with (n) numbers instead of three. For an interval ([l, r]), compute the count for (r) and subtract the count for (l-1).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 5e6 + 20;
const ll INF = 1e18;

struct Edge {
    int target, next;
    ll weight;
} edges[MAX << 2];
int head[MAX], edge_count = 0;
ll dist[MAX];
bool in_queue[MAX];

void add_edge(int u, int v, ll w) {
    edges[++edge_count] = {v, head[u], w};
    head[u] = edge_count;
}

void spfa(int start, int mod) {
    fill(dist, dist + mod, INF);
    memset(in_queue, 0, sizeof(in_queue));
    queue<int> q;
    q.push(start);
    in_queue[start] = true;
    dist[start] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;
        for (int i = head[u]; i; i = edges[i].next) {
            int v = edges[i].target;
            ll w = edges[i].weight;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!in_queue[v]) {
                    in_queue[v] = true;
                    q.push(v);
                }
            }
        }
    }
}

int main() {
    int n;
    ll l_bound, r_bound;
    cin >> n >> l_bound >> r_bound;
    vector<ll> numbers(n);
    for (int i = 0; i < n; i++) cin >> numbers[i];
    sort(numbers.begin(), numbers.end());
    ll base = numbers[0];
    for (int i = 0; i < base; i++) {
        for (int j = 1; j < n; j++) {
            add_edge(i, (i + numbers[j]) % base, numbers[j]);
        }
    }
    spfa(0, base);
    ll total = 0;
    for (int i = 0; i < base; i++) {
        if (dist[i] <= r_bound) {
            total += (r_bound - dist[i]) / base + 1;
        }
        if (dist[i] < l_bound) {
            total -= (l_bound - 1 - dist[i]) / base + 1;
        }
    }
    cout << total << endl;
    return 0;
}

An alternative method uses dynamic programming based on a complete knapsack approach modulo (m), with time complexity (O(n^2)) and simpler implementation.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 100;
const ll INF = 1e18;

int main() {
    int n;
    ll left, right;
    cin >> n >> left >> right;
    vector<ll> arr(n);
    bool has_zero = false;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        if (arr[i] == 0) has_zero = true;
    }
    if (has_zero) {
        cout << right - left + 1 << endl;
        return 0;
    }
    sort(arr.begin(), arr.end());
    ll modulus = arr[0];
    vector<ll> dp(modulus, INF);
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        ll g = __gcd(modulus, arr[i]);
        for (int start = 0; start < g; start++) {
            for (int current = start, cycles = 0; cycles < 2; cycles += (current == start)) {
                int next = (current + arr[i]) % modulus;
                dp[next] = min(dp[next], dp[current] + arr[i]);
                current = next;
            }
        }
    }
    ll answer = 0;
    for (int i = 0; i < modulus; i++) {
        if (right >= dp[i]) answer += (right - dp[i]) / modulus + 1;
        if (left > dp[i]) answer -= (left - 1 - dp[i]) / modulus + 1;
    }
    cout << answer << endl;
    return 0;
}