https://www.luogu.com.cn/problem/CF1139D
（暂时没有解释，咕咕咕~~~）
最重要的部分是对式子的化简，令 \(X\) 为步数：
\[\begin{align} E[X] &= \sum_jjP(X=j)\\ &= \sum_j\sum_i^j1P(X=j)\\ &= \sum_i\sum_{j\geq i}P(X=j)\\ &= \sum_iP(X\geq i)\\ &= 1+\sum_iP(X>i)\\ &= 1+\sum_i(1-P(\gcd_i(a_i)=1)) \\ &= 1+\sum_i\frac{m^i-\sum_{k\geq 1}\mu(k)\lfloor\frac{m}{k}\rfloor^i}{m^i}\\ &= 1+\sum_i\frac{m^i-m^i-\sum_{k\geq 2}\mu(k)\lfloor\frac{m}{k}\rfloor^i}{m^i}\\ &= 1-\sum_i\frac{\sum_{k\geq 2}\mu(k)\lfloor\frac{m}{k}\rfloor^i}{m^i}\\ &= 1-\sum_{k\geq 2}\mu(k)\sum_i\left(\frac{\lfloor\frac{m}{k}\rfloor}{m}\right)^i\\ &= 1-\sum_{k\geq 2}\mu(k)\frac{\lfloor\frac{m}{k}\rfloor}{m}\lim_{n\rightarrow \infty}\frac{1-(\frac{\lfloor\frac{m}{k}\rfloor}{m})^n}{1-\frac{\lfloor\frac{m}{k}\rfloor}{m}}\\ &= 1-\sum_{k\geq 2}\mu(k)\frac{\lfloor\frac{m}{k}\rfloor}{m}\frac{1}{1-\frac{\lfloor\frac{m}{k}\rfloor}{m}}\\ &= 1-\sum_{k\geq 2}\mu(k)\frac{\lfloor\frac{m}{k}\rfloor}{m-\lfloor\frac{m}{k}\rfloor}\\ \end{align} \]其中用了期望定义、容斥、莫反、等比数列求和公式。
标签：lfloor,geq,frac,sum,rfloor,mu,CF1139D From： https://www.cnblogs.com/Jack-YT/p/18311222