题目
采用类似某道 ABC 类似的题，直觉发现最大值肯定是每次都放回去，而最小值应该是每次都不放回去。
考虑最大值 \(E_1\) 怎么求。正难则反，设 \(P(x)\) 为操作 \(x\) 次游戏结束地概率，设 \(Q(x)\) 为操作 \(x\) 次游戏仍然没结束的概率。则 \(P(x)=Q(x-1)-Q(x)\)。
\[\begin{aligned}
E_1&=\sum_{k\ge 1} kP(k)\\
&=\sum_{k\ge 1}kQ(k-1)-kQ(k)\\
&=\sum_{k\ge 1}Q(k)(k+1-k)\\
&=\sum_{k\ge 1}Q(k)\\
\end{aligned}
\]
按照操作后的 \(\gcd\) 进行分类。\(f_i\) 为每次都放回去，操作若干次之后 \(\gcd\) 为 \(i(i\neq 1)\) 的概率，如果是 \(1\) 直接就计入期望，即 \(E_1=1+\sum_{i=2}^V f_i\)。
同理最小也可以类似地转化为 \(E_2=1+\sum_{i=2}^V g_i\)。\(g_i\) 为每次都放回去，操作若干次之后 \(\gcd\) 为 \(i(i\neq 1)\) 的概率。
对于这种题，考虑分析 \(\gcd\) 是 \(i\) 的倍数的情况。然后倒序 \(O(n \ln n)\) 容斥即可。
-
\(f_i\)：\(P=\dfrac{cnt_i}{n}\)，概率为 \(\sum_{k\ge 1} P^k=\dfrac{P}{1-P}\)。
-
\(g_i\)：\(\sum_{k=1}^{cnt_i} \dfrac{A_{cnt_i}^k}{A_n^k}=\dfrac{cnt_i!(n-k)!}{(cnt_i-k)!n!}\)
做完。