有意义的操作相当于：

• 花费 $1$ 代价将 $n$ 增加 $1$。
• 花费 $k+2$ 代价将 $n$ 变为 $kn$。

直接用二进制可以得到答案不超过 $5\log_2 n$。从 $n$ 开始倒着考虑，有用的状态也就都形如 $\left\lfloor \frac n x \right\rfloor$，每次转移是枚举除数 $k$，然后先减去 $n\bmod k$ 再除以 $k$。直接对这些状态进行 Dijkstra，因为答案很小，使用桶而不是二叉堆实现优先队列，时间复杂度 $O(\sqrt n\log n)$。