CF1139D Steps to One

Description

给一个数列，每次随机从 $[1,m]$ 中选择一个数添加到数列末尾，直至数列的 $\gcd =1$ 时停止。求期望长度。
$1\leq m\leq 10^5$

Solution

考虑求 $E(X)$ 的一种公式：

$E(X) = \sum_{i\ge 1}P(X\ge i)$

考虑 $P(X\ge i)$ 的意义：前 $i-1$ 个数的 $\gcd \ne 1$ 。
设 $f_i$ 表示前 $i$ 个数，$\gcd \ne 1$ 的方案数，则有

$f_i=-\sum_{d=2}^{m}\mu(d)(\lfloor\frac{m}{d}\rfloor)^i$

可以通过考虑枚举最后的 $\gcd$ 并容斥得到上式。
然后将 $f$ 带回到 $E(X)$ 的式子里，可以得到

$\begin{aligned} E(X)&=\sum_{i\ge 1}P(X\ge i)\\ &=\sum_{i\ge 1}\frac{f_{i-1}}{m^i}\\ &=-\sum_{i\ge 1}\frac{\sum\limits_{d=2}^{m}\mu(d)(\lfloor\frac{m}{d}\rfloor)^{i-1}}{m^i} \end{aligned}$

分数线上下的指数不统一不方便，我们考虑一下怎么统一。事实上只要让 $P$ 中的 >= 变成 > 即可。
因为长度至少为 $1$ ，所以有

$\begin{aligned} E(X)&=1+\sum\limits_{i\ge 1}P(X>i)\\ &=1-\sum_{i\ge 1}\frac{\sum\limits_{d=2}^{m}\mu(d)(\lfloor\frac{m}{d}\rfloor)^i}{m^i}\\ &=1-\sum_{d=2}^{m}\mu(d)\sum_{i\ge 1}(\frac{\lfloor\frac{m}{d}\rfloor}{m})^i \end{aligned}$

然后对于等比数列求和，我们有

$\sum_{i\ge 0}x^i = \frac{1-x^{+\infin}}{1-x} = \frac{1}{1-x}\ \ \ \ \ (x\in (-1,1))$

所以原式可以转化为

$\begin{aligned} E(X) = 1-\sum_{d=2}^{m}\mu(d)\frac{\lfloor\frac{m}{d}\rfloor}{m-\lfloor\frac{m}{d}\rfloor} \end{aligned}$

复杂度 $\mathcal{O}(m)$ 。

总结一下：在 OI 中出现了无穷项，应该果断往「等比数列」的形式上去靠。