题解：P15461 【MX-X25-T5】『FeOI-5』Flyway

· · 题解

一、明确题意

已知规则：每 b 个低阶货币换 a 个高阶，(a<b)。初始数量 n，能换必换是最优贪心，要最小化总货币数，等价于：把每一轮兑换拆成余数留存、商进位，最终总答案是所有留存余数之和。 换一种等价建模：设每一轮进位后的数量可以表示为 (k\cdot a)（第一步特判），每次变换：(k\leftarrow\left\lfloor\dfrac{k\cdot a}{b} \right\rfloor) 最终答案等价于统计整个迭代过程中所有经过的 k 的贡献和。

二、朴素暴力不行

直接一步步模拟迭代：每次 k 变小，但如果 b 极小、n 极大，迭代轮数会很高，朴素暴力会被卡。所以不能无脑逐轮模拟，要用阈值分治优化。

三、阈值分治

设阈值为 B（取 n^{1/3} 量级平衡复杂度），分两类处理：

  1. 小 b 情况：(b\le B)，b 很小，直接逐轮暴力模拟迭代过程即可。因为 b 小但阈值卡住上限，总迭代轮数被 B 限制，复杂度可控。
  2. 大 b 情况：(b>B) 此时有关键性质：初始 (k\le\left\lfloor\dfrac{n}{b}\right\rfloor)，本身 k 的初值就很小。且迭代中 k 的下降量单调不增，每一段会形成等差下降区间。 对每一段解不等式，直接批量跳过整段等差数列，不用一轮轮算：先解出当前 k 保持同一下降公差能连续迭代多少次，再批量累加这段所有 k 的贡献，最后直接跳到这段结束后的 k，进入下一段。

由于本质不同的公差数量只有 O(\sqrt{k}) 级别，大 b 部分复杂度极低。平衡后复杂度 O(n^\frac13)，稳过所有数据范围。
AI 使用说明：本规范在写作完成后使用 DeepSeek 进行了格式化。