Codeforces #548 (Div. 2) D. Steps to One

题目链接 https://codeforces.com/contest/1139/problem/D

f(k) 表示 a[1],...,a[k] 的最大公约数不是 1 的概率。然后答案是 1+f(1)+f(2)+f(3)+...。a[1],...,a[n] 的最大公约数是 1 和 a[1],...,a[k] 不能被 2,3,4,... 整除等价。所以由容斥原理可以计算 f(k)。

f(k,p) 是前 k 项是 p 的倍数的概率。

\begin{align}
\textit{answer} &= 1 - \sum_{k=1}^{\infty} \sum_{p=2}^{\infty} \mu(p) f(k,p) \\
&= 1 - \sum_{p=2}^{\infty} \mu(p) \sum_{k=1}^{\infty} f(k,p) \\
&= 1 - \sum_{p=2}^{\infty} \mu(p) \sum_{k=1}^{\infty} \heartsuit^k \\
&= 1- \sum_{p=2}^{\infty} \mu(p) \frac{\heartsuit}{1-\heartsuit}
\end{align}

如果不用默比乌斯函数，答案能写成以下。这里的 p, q, r, ... 走所有质数上。

\begin{align}
1+\sum_{k=1}^{\infty} \left(\sum_{p} f(k,p) - \sum_{p < q} f(k,pq) + \sum_{p < q < r} f(k,pqr) - \cdots \right)
\end{align}