题意

从 1 楼出发，每次只能向上跳 $x$、$y$ 或 $z$ 层（或回到 1 楼），统计不超过 $h$ 的可达楼层数。$h \le 2^{63}-1$，而 $x,y,z \le 10^5$。

思路

直接做卡在哪里

从 1 楼开始逐层标记可达性是正确做法，但 $h$ 可达 $9.2\times10^{18}$：标记数组开不出，BFS 队列也装不下。这里的障碍不是“搜索太慢”，而是状态空间本身太大，所以必须先换状态，而不是优化搜索。

该压缩的维度是“楼层”

三个步长都很小，所以可枚举的量是步长而不是楼层。

关键抓手是同余。模 $b$ 的同余关系是等价关系，把所有楼层分成 $b$ 个等价类，也就是商集 $\mathbb{Z}/b\mathbb{Z}$。于是：

这一求和是合法的，因为同余分类是划分，每个楼层属于且仅属于一个类，不会重复计算。

为什么选最小步长当模

三个步长都能当模，选最小只是为了图小。$h=100$、步长 $[3,5,8]$ 时实测：

答案完全相同，区别只在余数类数量，也就是图上点数。所以取 $\min$。

但 $b$ 必须是 $\{x,y,z\}$ 之一，这是硬性前提。 取非步长的值（例如 4）会破坏“从 $L$ 加 $b$ 到 $L+b$”这条推导：

为什么按余数类计数不漏

“每类只需记 $\text{dist}[r]$”这句话必须双向证完才能用来计数。两个方向各证一次。

方向一（不多）：公式生成的每个楼层都真的可达。

这是构造性的。$\text{dist}[r]$ 是 Dijkstra 求出的某个真实路径终点，而 $b$ 是合法步长，所以从 $\text{dist}[r]$ 连续跳 $k$ 次 $b$ 得到 $\text{dist}[r]+kb$，每一步都合法。因此公式列出的楼层全部可达，不会多算。

方向二（不漏）：任何可达楼层都能写成 $\text{dist}[r]+kb$。

这里用反证。设 $L$ 是一个可达楼层，令 $r = L \bmod b$，则 $L$ 与 $\text{dist}[r]$ 同余。按 $\text{dist}[r]$ 的最小性有 $\text{dist}[r] \le L$，于是 $L-\text{dist}[r]$ 是 $b$ 的非负倍数：

反证落在哪里：假设 $L$ 不在任何 $\text{dist}[r]+kb$ 里，只有两种可能。

• 若 $\text{dist}[r] > L$：但 $L$ 本身是一个模 $b$ 余 $r$ 的可达楼层，它比 $\text{dist}[r]$ 更小，与“$\text{dist}[r]$ 是同类最小”矛盾。
• 若 $L-\text{dist}[r]$ 不是 $b$ 的倍数：但两者都 $\equiv r \pmod b$，同余的两个数之差必被 $b$ 整除，矛盾。

两种可能都不成立，所以 $L$ 一定在公式里。也就是说，漏掉一个可达楼层等于承认 $\text{dist}[r]$ 不是同类最小，与 Dijkstra 的正确性冲突。

两边夹住——方向一保证不多、方向二保证不漏——所以计数恰好等于可达楼层数。

举个例子：拼一个具体楼层

取 $h=100$、步长 $[3,5,8]$、$b=3$，考虑 $L = 1+3+3+5+5 = 17$。

所以 $L = \text{dist}[2] + 2b$，它落在“余数 2”那一类的公式里。

从构造上看更清楚：$\text{dist}[2] = 11$ 可由 $1+5+5$ 得到，再跳两次 $3$ 就是 $17$。原本的 $3$ 夹在中间，重排成 $1+5+5$ 再 $+3+3$ 仍然合法——加法可交换，且每种步长的使用次数不限，所以“先拼出同类最小、再补若干个 $b$”这个拆法总是可行的。

逐类核对（$h=100$、步长 $[3,5,8]$）：

余数 2 那行最能说明问题：$2,5,8$ 都 $\equiv 2 \pmod 3$ 却都不可达，而从 $11$ 起同类楼层全部可达——分界恰好就在 $\text{dist}$ 处。

为什么“最早可达楼层”可以用最短路求

把一步 $s$ 作用到余数上，是一个平移：

它在 $\mathbb{Z}_b$ 里是封闭的加法。于是整张图就是循环群 $\mathbb{Z}_b$ 关于生成集 $\{x \bmod b,\ y \bmod b,\ z \bmod b\}$ 的 Cayley 图（有向，边权为 $s$）：

图上一条路径对应一串真实跳跃，路径权和就是楼层增量。所以

这个视角顺带说清了两个问题：顶点数为什么是 $b$（$|\mathbb{Z}_b| = b$，取最小步长让图最小），为什么能跑（每点只有 3 条出边，与楼层规模无关）。

求 $\text{dist}$ 是单源最短路，用堆优化 Dijkstra，$O(b \log b)$。

起点是 1，不是 0

从 1 楼出发，所以 $\text{dist}[1 \bmod b] = 1$。这一步写成 0 会多算一层：

1
2h=15, 步长 [4,7,9]     起点 1 → 9（正确）
                      起点 0 → 10（错）

因为楼层从 1 开始，1 楼本身就可达。

计数

每个余数类独立贡献：

样例 1（$h=15$、步长 $[4,7,9]$）展开验证：

合计 9 层，与题面给出的 $\{1,5,8,9,10,12,13,14,15\}$ 完全一致。

Python 知识

• 余数图只有 $\min(x,y,z)$ 个节点，与 $h$ 无关。
• Python 整数直接支持 $2^{63}$ 范围，不必像 C++ 那样用 unsigned long long。
• 生成器求和只统计 $\text{dist}[r] \le h$ 的余数；否则 $(h-\text{dist}[r])$ 为负，会多算。
• 堆里用 current != distance[residue] 跳过过期条目，与普通 Dijkstra 一致。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-17 01:40
# update_at: 2026-10-21 09:10
#
# main.py：跳楼机。从 1 楼出发，每次可向上跳 x/y/z 层，统计不超过 h 的可达楼层数。
# h 可达 2^63-1，逐层标记不可行；但三个步长都 <= 1e5，所以该压缩的维度是"楼层"。
# 取最小步长 base，把所有楼层按模 base 的余数分成 base 个等价类（商集 Z/baseZ）。
# 同一类里一旦能到 L，则 L+base、L+2base 也都能到——前提是 base 本身是合法步长。
# 所以每类只需知道最早可达楼层 dist[r]，其余全部由「加 base」生成。
# 把一步 s 作用到余数上是平移 r -> (r+s) mod base，它在 Z_base 里封闭，
# 于是整张图就是循环群关于生成集 {x mod base, y mod base, z mod base} 的 Cayley 图：
# 点 base 个、每点 3 条出边，与 h 的规模完全无关。在此基础上跑 Dijkstra 求 dist。
# 最后每类贡献 floor((h-dist[r])/base)+1 层；同余分类是划分，按类求和不会重复。

import sys
from heapq import heappop, heappush

INF = 1 << 62  # 整数哨兵；Python int 任意精度，不必担心 h + step 溢出


def earliest_reachable(height: int, steps: list[int]) -> list[int]:
    """返回 dist：dist[r] 为「模 base 余 r」这一类里的最早可达楼层。

    base 取 min(steps)：它必须是合法步长（否则「加 base 仍可达」不成立），
    取最小只是为了让余数图最小。
    """
    base = min(steps)

    dist = [INF] * base
    start = 1 % base
    dist[start] = 1  # 起点是 1 楼，不是 0

    heap: list[tuple[int, int]] = [(1, start)]  # (楼层, 余数)，楼层在前才能按它比大小

    while heap:
        current, residue = heappop(heap)
        if current != dist[residue]:
            continue  # 堆里的过期记录

        for step in steps:
            next_residue = (residue + step) % base
            candidate = current + step
            if candidate < dist[next_residue]:
                dist[next_residue] = candidate
                heappush(heap, (candidate, next_residue))

    return dist


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    height = next(data)
    steps = [next(data), next(data), next(data)]

    dist = earliest_reachable(height, steps)
    base = min(steps)

    # 每个余数类独立贡献：最早可达楼层之后，每加一次 base 仍可达。
    # 必须过滤 dist > height，否则 (height - dist) 为负会多算。
    print(sum((height - value) // base + 1 for value in dist if value <= height))


if __name__ == "__main__":
    solve()

原有 C++ 版本仍保留：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-17 01:40
 * update_at: 2026-10-21 09:10
 */
// 跳楼机：从 1 楼出发，每次可向上跳 x/y/z 层，统计不超过 h 的可达楼层数。
// h 可达 2^63-1，逐层标记不可行；但三个步长都 <= 1e5，所以该压缩的维度是"楼层"。
// 取最小步长 base，把所有楼层按模 base 的余数分成 base 个等价类（商集 Z/baseZ）。
// 同一类里一旦能到 L，则 L+base、L+2base 也都能到——前提是 base 本身是合法步长。
// 所以每类只需知道最早可达楼层 dist[r]，其余全部由「加 base」生成。
// 把一步 s 作用到余数上是平移 r -> (r+s) mod base，它在 Z_base 里封闭，
// 于是整张图就是循环群关于生成集 {x mod base, y mod base, z mod base} 的 Cayley 图：
// 点 base 个、每点 3 条出边，与 h 的规模完全无关。在此基础上跑 Dijkstra 求 dist。
// 最后每类贡献 floor((h-dist[r])/base)+1 层；同余分类是划分，按类求和不会重复。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXB = 100000 + 5;  // base = min(x,y,z) <= 1e5

ll h;                 // 楼层上限，可达 2^63-1
int step[3];          // 三个步长 x, y, z
int base_len;         // base = min(step)，同时是余数类数量
ll dist_arr[MAXB];    // dist_arr[r]：模 base 余 r 这一类里的最早可达楼层

const ll INF = (1LL << 62);

void dijkstra() {
    for (int r = 0; r < base_len; r++) dist_arr[r] = INF;

    // 起点是 1 楼，不是 0：楼层从 1 开始，1 本身可达
    int start = 1 % base_len;
    dist_arr[start] = 1;

    // (楼层, 余数) 的小根堆
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> heap;
    heap.push({1, start});

    while (!heap.empty()) {
        ll current = heap.top().first;
        int residue = heap.top().second;
        heap.pop();

        if (current != dist_arr[residue]) continue;  // 堆里的过期记录

        for (int i = 0; i < 3; i++) {
            int s = step[i];
            int next_residue = (residue + s) % base_len;
            ll candidate = current + s;
            if (candidate < dist_arr[next_residue]) {
                dist_arr[next_residue] = candidate;
                heap.push({candidate, next_residue});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> h;
    for (int i = 0; i < 3; i++) cin >> step[i];

    base_len = min(step[0], min(step[1], step[2]));

    dijkstra();

    // 每个余数类独立贡献：最早可达楼层之后，每加一次 base 仍可达
    ll answer = 0;
    for (int r = 0; r < base_len; r++) {
        if (dist_arr[r] <= h) {
            answer += (h - dist_arr[r]) / base_len + 1;
        }
    }

    cout << answer << '\n';
    return 0;
}

复杂度

设 $b = \min(x,y,z) \le 10^5$。点数 $b$、每点 3 条出边，堆优化 Dijkstra 为 $O(b \log b)$，空间 $O(b)$。与 $h$ 的规模 $2^{63}$ 完全无关——这正是压缩维度的收益。

总结

这道题的完整链条是三段，缺一不可：

1. 同余类给出有限的状态空间（$b$ 个等价类，且是同余划分，所以按类求和不会重复）；
2. 类上的加法封闭把它变成循环群的 Cayley 图，每点只有 3 条出边；
3. $b$ 是合法生成元，所以“代表元加 $b$ 仍在同一类且仍可达”，每类只需记最早可达楼层。

识别信号：题目出现「巨大范围 + 少量固定增量」并问可达数量，就该想同余最短路。接着问两件事——拿哪个量取模（最小的那个，且必须是合法增量），类内最小值和其余值如何互相转化（加一次模数）。