# 题目描述

小 P 有一个奇怪的秒表。若这个秒表当前时间为 $t$，则一秒后它的时间 $t$ 将变为 $[0,t−1]$ 中的随机一个整数。小 P 想知道，当秒表的初始时间（即第 $0$ 秒的时间 $t$）为 $t_0$ 时，其时间 $t$ 平均会在第几秒时变为 $0$。

# 输入格式

第一个数为数据组数 $T$。

接下来 $n$ 行，每行 $1$ 个整数 $t_0$。

# 输出格式

对于每组数据，输出一个小数，为时间 $t$ 平均会在第几秒时变为 $0$。

本题采用特判，只要你的程序输出的答案与正解之间的差值不超过 $0.01$ 即算正确，输出的每个数之间用任何空白符间隔均可。

# 输入样例

3

1

2

3

# 输出样例

1.000000

1.500000

1.833333

# 数据范围

对于 $30$ 的样例，保证 $0≤T×t^2_0≤4×10^6$。

对于 $60$ 的样例，保证 $0≤t_0≤2000$。

对于 $90$ 的样例，保证 $0≤t_0≤2×10^6$。

对于 $100$ 的样例，保证 $0≤t_0≤10^{12}$，$0<T≤2×10^5$。

# 提示

设 $a_i$ 为 $t_0=i$ 时秒表平均变为 $0$ 所用的时间，总有：

$$a_n=\frac {a_0+a_1+ \cdots +a_{n−1}} n + 1$$

# 题解：数学

设 $sum_n$ 为 $a_n$ 前缀和。则：

$$sum_n - sum_{n - 1} = \frac {sum_{n - 1}} n + 1 \\ sum_n = \frac {n + 1} n sum_{n - 1} + 1 \\ \frac {sum_n} {n + 1} = \frac {sum_{n - 1}} n + \frac 1 {n + 1} \\ sum_n = (n + 1) \left( \frac 1 2 + \cdots + \frac 1 {n + 1} \right) = \frac {n + 1} 2 + \cdots + 1 \\ sum_{n - 1} = n \left( \frac 1 2 + \cdots + \frac 1 n \right) = \frac n 2 + \cdots + 1 \\ a_n = sum_n - sum_{n - 1} = 1 + \frac 1 2 + \frac 1 3 + \cdots + \frac 1 n$$

由于 $n$ 最大可以到 $10^{12}$，所以我们需要一个结论：

$$\lim_{n \to \infty} (a_n - \ln n) = \gamma$$

其中 $\gamma$ 是欧拉常数，你可以通过打表前 $10^6$ 项计算出，这里给出六位小数：$0.577216$。

因此小范围直接预处理出来，大范围的答案直接利用该结论。

参考代码：

#include <stdio.h>

#include <math.h>

#define GAMMA 0.577216

typedef long long ll;

double sum[1000010];

int main()

{

    // freopen("U.in", "r", stdin);

    // freopen("U.out", "w", stdout);

    for (int i = 1; i <= 1000000; ++ i)

        sum[i] = sum[i - 1] + 1.0 / i;

    int T;

    scanf("%d", &T);

    while (T -- )

    {

        ll t;

        scanf("%lld", &t);

        if (t <= 1000000)

            printf("%.4lf\n", sum[t]);

        else

            printf("%.4lf\n", log(t) + GAMMA);

    }

    return 0;

}