原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：可达数量
1.2 题目背景、允许、禁止与限制
背景：有一栋 hhh 层的摩天大楼
允许：初始在 111 层，有四种操作供选择：
* 向上 xxx 层
* 向上 yyy 层
* 向上 zzz 层
* 回到 111 层
求可到达的楼层数量
禁止：
限制：
1.3 题目数据范围与猜测
1≤x,y,z≤105⟶O((x,y,z) log (x,y,z))1 \le x,y,z \le 10^5 \longrightarrow O((x,y,z)~log~(x,y,z))1≤x,y,z≤105⟶O((x,y,z) log (x,y,z))
1.4 一句话概括题意
有一栋 hhh 层的摩天大楼，有四种操作，求可到达的楼层数量
2 题目破题推导
2.1 题意梳理
初始位置为第 111 层，允许四种操作：
1. 当前楼层 uuu 向上走 xxx 层至 u+xu+xu+x；
2. 当前楼层 uuu 向上走 yyy 层至 u+yu+yu+y；
3. 当前楼层 uuu 向上走 zzz 层至 u+zu+zu+z；
4. 任意楼层直接返回第 111 层。
所有楼层 vvv 必须满足 1≤v≤h1\le v \le h1≤v≤h，求可到达楼层的总数量。
2.2 数学表达式化简
任意合法路径均为为：从1出发，累加若干次 x,y,zx,y,zx,y,z。
因此所有可达楼层满足：
pos=1+a⋅x+b⋅y+c⋅z(a,b,c∈N)pos = 1 + a\cdot x + b\cdot y + c\cdot z \quad (a,b,c\in \mathbb{N}) pos=1+a⋅x+b⋅y+c⋅z(a,b,c∈N)
使 A=ax+by+czA = ax+by+czA=ax+by+cz，H=h−1H=h-1H=h−1，原问题等价于：统计满足 0≤A≤H0\le A \le H0≤A≤H 的非负整数 AAA 的个数。
2.3 同余分类优化思路
选取 xxx 作为模数，任意非负整数 AAA 可唯一表示为：A=k⋅x+r,r∈{0,1,2,…,x−1}A = k\cdot x + r,\quad r\in\{0,1,2,\dots,x-1\}A=k⋅x+r,r∈{0,1,2,…,x−1}，其中 rrr 为 A mod xA~mod~xA mod x
对固定余数 rrr：
设 dis[r]dis[r]dis[r] 为满足 A≡r(modx)A\equiv r \pmod{x}A≡r(modx) 的最小合法 AAA。
若 dis[r]≤Hdis[r] \le Hdis[r]≤H，则该余数下合法数字为：dis[r],dis[r]+x,dis[r]+2x,⋯≤Hdis[r],dis[r]+x,dis[r]+2x,\dots \le Hdis[r],dis[r]+x,dis[r]+2x,⋯≤H，总数为 H−dis[r]x+1\dfrac{H-dis[r]}{x}+1xH−dis[r] +1；若 dis[r]>Hdis[r]>Hdis[r]>H，该余数无合法数字。
问题转化为：求解每个余数 rrr 对应的最小 dis[r]dis[r]dis[r]。
2.4 数学模型向图论模型的转化
2.4.1 顶点定义
构造有向图 G=(V,E)G=(V,E)G=(V,E)，顶点集合 V={0,1,2,…,x−1}V=\{0,1,2,\dots,x-1\}V={0,1,2,…,x−1}。
顶点 rrr 的含义：代表所有模 xxx 余 rrr 的整数 AAA。
2.4.2 边的定义
对任意余数 iii，若给当前总和 AAA 加上 yyy，新总和为 A+yA+yA+y，新余数为 (i+y) mod x(i+y)\bmod x(i+y)modx，边权为 yyy；
同理加上 zzz 后余数为 (i+z) mod x(i+z)\bmod x(i+z)modx，边权为 zzz。
因此对每个顶点 iii，添加两条带权有向边：
i→w=y(i+y) mod xi→w=z(i+z) mod x\begin{align*} i &\xrightarrow{w=y} (i+y) \bmod x \\ i &\xrightarrow{w=z} (i+z) \bmod x \end{align*} ii w=y (i+y)modxw=z (i+z)modx
边权代表累加的数值大小
2.4.3 模型等价性证明
1. 起点：顶点 000，对应 A=0A=0A=0（即原始楼层 111）；
2. 单源最短路 dis[r]dis[r]dis[r] 的意义：从顶点 000 走到顶点 rrr 的最短路径总权值，恰好是满足 A≡r(modx)A\equiv r \pmod{x}A≡r(modx) 的最小 AAA；
3. 原计数问题等价于：跑完单源最短路后，遍历所有余数，累加每类余数的合法数字数量。
2.5 两种图模型对比
1. 暴力楼层图（不可行）
* 顶点：每层楼层 1∼h1\sim h1∼h，h≤263−1h\le 2^{63}-1h≤263−1，顶点规模极大，无法存储遍历；
* 边：u→u+x,u→u+y,u→u+z,u→1u\to u+x,u\to u+y,u\to u+z,u\to1u→u+x,u→u+y,u→u+z,u→1；
* 缺陷：无法适配题目超大范围的 hhh。
2. 余数剩余类图（本题采用）
* 顶点：仅 xxx 个（x≤105x\le 10^5x≤105），内存可承受；
* 边：总边数 2x2x2x，图规模极小；
* 优势：将无穷多数字按余数压缩为有限顶点，完美匹配数据范围。
3 模型匹配
> 格式为："关键词：...... ⟶\longrightarrow⟶ ......\huge{......}......"
关键词：最短路，无负边，h≤105h\le 10^5h≤105 ⟶\longrightarrow⟶ 堆优化dijkstra\huge{堆优化dijkstra}堆优化dijkstra
4 最终代码（禁止抄袭，仅用于参考）
