考慮一個選擇 $x_1, x_2, \cdots x_k \mid x_{k + 1}$, 其中 $\gcd(x_1, x_2, \cdots, x_k) \neq 1$, 而 $\gcd(x_1, x_2, \cdots, x_k, x_{k + 1}) = 1$, 我們取到其的概率是 $\dfrac{1}{n^{k + 1}}$, 事實上我們就需要找到所有的情形并計算概率與 $k$ 的乘積之和

考慮怎么處理到所有的情形, 一種想法是 $\rm{dp}$
常用的方法是 $f_{i, j}$ 表示選擇到第 $i$ 個數, 且存在一個公約數是 $i$ 的第 $j$ 個質因數這樣一種情形的概率$($本質上是單個數的不同質因數個數有限$)$
這個方法是有問題的, 但是不妨先列出一下轉移
$$\begin{gather*} f_{i, x} \stackrel{t}{\longleftarrow} \frac{1}{n^t} f_{j, y} & p_{i, x} = p_{j, y} \end{gather*}$$
然后我們要計算選擇一個 $x_{k + 1}$ 的概率來完成這個形態
需要注意的是, 這是一個無窮項求和, 但是并不困難

問題出在哪? 不難發現對于 $\gcd(x_1, x_2, \cdots, x_k)$ 不為一個質數的情況, 我們顯然會算重
當然不難猜測去重是一個容斥的形式, 但是這樣子計算復雜度不能保證, 而且由于 $x_{k + 1}$ 的存在, 算重的部分也不好處理

因此我們考慮換成另一種常見的處理方法, 即枚舉一個約數
考慮欽定最終 $\gcd(x_1, x_2, \cdots, x_k) = g$, 不妨找到 $g$ 的倍數集合 $\mathbb{S}$, 則每次我們選擇集合內外的概率分別已知, 剩下的就是一個無窮項求和, 可以用等比數列求和公式計算

具體的, 記 $p(x)$ 表示在 $n$ 個數中選出 $a_i = x$ 的概率, 求 $f(x)$ 表示欽定最終 $\gcd(x_1, x_2, \cdots, x_k) = x$, 找到的形態概率之和
$$P(x) = \sum_{x|y} p(y) \\ x > 1, \quad f(x) = \sum_{i=1}^{+\infty} P^i(x)$$

這樣仍然會算重, 但是去重是很簡單的, 我們只需要倒序處理, 然后每次處理掉 $x$ 倍數即可
即
$$P(x) = \sum_{x|y} p(y) \\ x > 1, \quad f(x) = \sum_{i=1}^{+\infty} P^i(x) - \sum_{x|y} f(y) \\$$

到這里我發現我對期望的計算還有問題, 讓我們來處理這一部分
不妨同樣設置 $P$ 函數, 但是先不管去重
$$\begin{align*} f(x) &= \Big\{1 - P(x)\Big\}\sum_{i=1}^{+\infty} iP^i(x) \\ &= \Big\{1 - P(x)\Big\}\sum_{i=1}^{+\infty} \sum_{j = i}^{+\infty} P^j(x) \\ &= \Big\{1 - P(x)\Big\}\sum_{i=1}^{+\infty} \frac{P^i(x)}{1 - P(x)} \\ &= \sum_{i=1}^{+\infty} P^i(x) \\ \end{align*}$$

進而我們可以輕松地完成這一工作