(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} \]