题解

思路

令 $T$ 为停止时的长度。由尾和公式，$\mathbb E(T)=\sum_{k\ge0}\Pr(T>k)$。前 $k$ 次选择后仍未停止，等价于这 $k$ 个数的最大公约数大于一。

做法

设 $q_d=\lfloor m/d\rfloor$。用莫比乌斯反演，$k\ge1$ 次选择后的最大公约数等于一的概率为

$$\sum_{d=1}^m\mu(d)\left(\frac{q_d}{m}\right)^k.$$

利用等比数列求和，得到

$$\mathbb E(T)=1-\sum_{d=2}^m\mu(d)\frac{q_d}{m-q_d}.$$

在线性筛中求出所有 $\mu(d)$，再按上式计算即可。小范围可以把每个当前最大公约数视为马尔可夫状态解线性方程；中等范围可以直接枚举下一次选择并按状态从小到大递推。

正确性说明

莫比乌斯反演恰好把“所有数均被 $d$ 整除”的事件组合成“最大公约数等于一”的事件。尾和公式枚举了停止前的每个时刻；对每个 $d\ge2$ 的概率幂级数求和后恰为 $q_d/(m-q_d)$。因此公式完整且不重不漏地给出停止长度的期望。

复杂度

时间复杂度 $O(m\log\log m)$，空间复杂度 $O(m)$。