小猪佩奇玩游戏
题目描述
佩奇和乔治玩游♂戏。
佩奇在黑板上写下数字 $\{1,2,\cdots,n\}$ ,每次他们会等概率地报出黑板上的一个数字 $x$ ,并删除所有 $x$ 的正整数次幂。
形式化地,给定数列 $\{1,2,\cdots,n\}$ ,每次等概率选出数列中存在的 $1$ 个数字 $x$ ,并将形如 $\{x^k,k \in Z^{+}\}$ 的数字删除。
他们玩了整整一个下午,游戏还是没有结束,所以他们想知道,该游戏期望在多少轮后会结束。
如果你的答案与正确答案的绝对误差在 $10^{-4} $以内,则被判定为正确。
输入输出格式
输入格式
第一行 $1$ 个正整数 $t$,表示佩奇和乔治打算玩 $t$ 轮游戏。
之后 $t$ 行,每行 $1$ 个正整数 $n$,表示佩奇在黑板上写下了数字 $\{1,2,\cdots,n\}$ 并将进行游戏。
输出格式
一共 $t$ 行,每行 $1$ 个小数,表示答案,答案保留小数。
如果你的答案与正确答案的绝对误差在 $10^{-4}$以内,则被判定为正确。
输入输出样例
输入样例 #1
5
4
8
16
32
100
输出样例 #1
3.50000000
7.00000000
13.83333333
28.33333333
93.41666667
说明
对于 $n=4$,
若删除的顺序为 $\{1,2,3\},\{3,2,1\}$, 那么概率为$\frac{1}{4} \times \frac{1}{3} \times \frac{1}{1}=\frac{1}{12}$
若删除的顺序为 $\{1,3,2\},\{3,1,2\}$, 那么概率为$\frac{1}{4} \times \frac{1}{3} \times \frac{1}{2}=\frac{1}{24}$
若删除的顺序为 $\{2,1,3\},\{2,3,1\}$, 那么概率为$\frac{1}{4} \times \frac{1}{2} \times \frac{1}{1}=\frac{1}{8}$
对于剩余的 $12$ 种删除了 $4$ 次的序列,概率为$\frac{1}{4} \times \frac{1}{3} \times \frac{1}{2} \times \frac{1}{1}=\frac{1}{24}$
容易发现答案即为
$\frac{2 \times 3}{12} + \frac{2 \times 3}{24}+\frac{2 \times 3}{8} + \frac{12 \times 4}{24}=\frac{7}{2}=3.50000$
### 数据范围
对于 $20\%$ 的数据, $n \leq 10$
对于 $60\%$ 的数据, $n \leq 10^5$
对于 $100\%$ 的数据, $n \leq 10^9,t \leq 100$
### 出题人善意的提醒
对于 C++ 选手,若对于正整数 $n,k$,希望得到 $\sqrt[k] n$,请尽量不要使用 C++ 自带的 $\operatorname{pow}$ 函数,以免可能产生不必要的精度误差。