自动搬运

查看原文

来自洛谷，原作者为

	Jadonyzx awmc

搬运于2025-08-24 23:01:30，当前版本为作者最后更新于2025-07-25 15:38:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注意到一次如果不考虑往更大的数字的跳跃，显然可以建出一个有向无环图跑拓扑排序即可，因此我们考虑将原转移转换为有向无环图上的动态规划。

难点在 $+1$ 操作上。

可发现，该操作只能与向因子移动组合在一起使用，不妨考虑在点 $i$ 时可以向哪些 $j$ 连接一条表示先进行若干次 $+1$ 再进行一次走向因子的边。

容易发现，这与之前到过的最小的比 $i$ 大的点有关。

考虑建分层图， $id_{i,j}$ 表示当前在 $i$ 点，之前到过的最小的比 $i$ 大的点为 $j$ 的点。

连边如下：

$id_{i,j}$ 连向 $id_{i-1,i}$ 表示减一操作。

$id_{i,j}$ 连向 $id_{k,i}$，其中 $k\mid i$。

$id_{i,j}$ 连向 $id_{k,i}$ ，其中存在 $j-1\geq q\geq i+1$ 且 $k\mid q$。

前两者复杂度优秀，第三个可以后缀和优化建图。

然后发现空间超限了。

打表发现答案在 __int128 范围内，较大数据打表即可。