考虑 DP，设 $f_i$ 为当前所有数的期望归 $1$ 步数，有

$$f_i = 1 + \frac{1}{n} \sum_{j=1}^n f_{\gcd(i,j)}$$

考虑 mobius 反演，

$$\begin{aligned} n(f_i - 1) &= \sum_{j=1}^n f_{\gcd(i,j)} \\ &= \sum_{d \mid i} \sum_{j=1}^n f_{d} [ gcd(i, j) = d] \\ &= \sum_{d \mid i} f_d \sum_{u \mid i/d} \mu(u) \left\lfloor \frac{n}{ud} \right\rfloor \end{aligned} $$

拿到这个式子还不能转移，可能存在 $d=i$ 的情况，总之筛一下因子就成。