(cf1139d) Steps to One

原题链接

思路:

由题意, 可得:

$$\begin{aligned} \require{extpfeil} P(l \le n) = & \frac{\sum_{a_1=1}^{m} \cdots \sum_{a_n=1}^{m}[(a_1,\cdots,a_n)=1]}{m^n} \\ = & \frac{\sum_{a_1=1}^{m} \cdots \sum_{a_n=1}^{m}\sum_{d|(a_1,\cdots,a_n)}\mu(d)}{m^n} \\ = & \frac{\sum_{d=1}^{m}\mu(d)\lfloor m/d \rfloor^n}{m^n} \\ P(l > n) = & 1 - \frac{\sum_{d=1}^{m}\mu(d)\lfloor m/d \rfloor^n}{m^n} \\ E \xlongequal{(1)} & \sum_{i=0}^{\infty} P(l>i) \\ = & 1 + \sum_{i=1}^{\infty} \left( 1 - \frac{\sum_{d=1}^{m}\mu(d)\lfloor m/d \rfloor^i}{m^i} \right) \\ \xlongequal{(2)} & 1 - \sum_{i=1}^{\infty}\sum_{d=2}^m \frac{\mu(d)\lfloor m/d \rfloor^i}{m^i} \\ = & 1 - \sum_{d=2}^m \mu(d) \sum_{i=1}^{\infty} \left( \frac{\left\lfloor m/d \right\rfloor}{m} \right)^i \\ = & 1 - \sum_{d=2}^{m} \mu(d) \frac{\frac{\lfloor m/d \rfloor}{m}}{1-\frac{\lfloor m/d \rfloor}{m}} \\ = & 1 - \sum_{d=2}^{m} \mu(d) \frac{\lfloor m/d \rfloor}{m - \lfloor m/d \rfloor} \\ \end{aligned}$$

使用数论分块计算即可.

其中(2)为提取$d=1$的项消除前面的$1$; (1)如下:

$$\begin{aligned} E = & \sum_{i=1}^{\infty} iP(l=i) \\ = & \sum_{i=1}^{\infty} P(l=1)\sum_{j=0}^{i-1}1 \\ = & \sum_{j=0}^{\infty}\sum_{i>j} P(l=i) \\ = & \sum_{j=0}^{\infty} P(l>j) \end{aligned}$$