COGS 不支持 Markdown，有些格式用不了，推荐到我的博客阅读。

Observation 1：从大到小，遇到 1 就操作，这样的操作次数最少。

证明：显然。

Observation 2：设上述结论得出的操作序列为 $p_1\sim p_m$，则对于每一次随机操作，如果操作的 $i\in p$，则 $m\gets m-1$，反之 $m\gets m+1$。

证明：因为操作顺序不影响结果，所以若 $i\in p$，则最少操作次数 -1。

反之手动模拟，如果 $i\notin p$，那么操作序列就要新增 $i$，操作次数 +1。

也就是说，答案只和 $m$ 的大小有关。

据此，设 $f_i$ 表示当前状态最少操作次数为 $i$ 时的期望答案。

有：

$$\begin{cases}f_i=i, & i\le k\\f_i=\frac{i}{n}f_{i-1}+\frac{n-i}{n}f_{i+1}+1, & \rm Otherwise\end{cases}$$

不知道有没有 MO 大神能解这个函数方程阿，反正我搞不出来这个东西，讲一下在洛谷题解里看到的神奇方法。

（upd：看到一种叫线性高消的神奇做法，算是高斯消元的变种，因为每个方程只有 3 项，所以可以 $\mathcal O(n)$ 算出来方程组的解）

考虑转化为更一般的形式，通常来讲期望递推都可以化简为 $f_i=f_{i-1}+b_i$ 的形式。

那么不妨设 $b_i=f_i-f_{i-1}$ 即 $f_i=f_{i-1}+b_i$，其中 $b_i$ 未知，把它带进方程解出来：

$$\begin{aligned}f_i & =\frac{i}{n}f_{i-1}+\frac{n-i}{n}f_{i+1}+1\\& = \frac{i}{n}(f_{i}-b_i)+\frac{n-i}{n}(f_i+b_{i+1})+1\end{aligned}$$

化简得：

$$b_i=\frac{(n-i)b_{i+1}+n}{i}$$

显然，$f_n=f_{n-1}+1$，故 $b_n=1$，先递推出 $b$，然后再推 $f$ 即可。

因为要求 $1\sim n$ 的约数，故时间复杂度为 $\mathcal O(n\ln n)$