推荐原文阅读

$\Theta(T\log^2 n)$的解法，搞了我半个下午才弄出来

蒟蒻的我反复看了几遍视频讲解，并经过反复推敲，终于弄懂了$\log^2$的做法

以下题解主要是对$memset0$巨佬题解的补充说明，尤其是高能部分，这里重点讲解具体如何计算大小为$i$的集合个数，至于计算删除大小为$i$的集合的期望次数可以见其它题解，已经讲的很清楚了

• $\sqrt n$的做法，复杂度的瓶颈在于计算有多少个大小为$i$的集合

• 大小为$i$的集合应该是$\lfloor n^{\frac{1}{i} }\rfloor$个，考虑集合中最小的数字$x$，那么$x^i \le n$, 则$x \le \lfloor n^{\frac{1}{i} }\rfloor$

• 由于$1^{\text{任意次方}} = 1$, 所以$1$提出来单独计算，故上面计算出的个数还要再$-1 $

• 表示我们可以把$2 \sim x$的数作为那些集合的首项(集合中最小的元素), 例如$i = 2, x = 4$, 那么集合就有$\text{{2, 4}, {3, 9}, {4, 16}}$

• 但是我们发现，其实像${2, 4}, {4, 16}$的集合不一定是极大的，它可能被包含在${2, 4, 8, 16}$这样的集合中

• 不是极大的集合意味着它可以扩张到更大的集合，而且它不是独立的，与外部有连边

• 为了去除那些不合法的集合(不是极大的集合), 问题转化为如何计算一个集合被更大的集合包含了多少次，我们要从答案中减掉这些不合法的贡献

• 对于一个确定的集合$S$，该集合的大小为$a$, 最小元素为$x$, 设较小集合的大小为$b$, 在较大集合中出现了$k$次($k$即是我们想求的)， 我们考虑较小集合的首项(较小集合中最小的元素) $y = x^k(y \in S)$， 例如$S = {2, 4, 8, 16}$，则$a = 4, x = 2$，当$b = 2$时，$y = 2, 4$

• 可知较小集合的最大元素是$y^b$, 并且由于$y^b \in S$, 则

$$y^b \le x^a$$

$$x^{kb} \le x^a$$

$$kb \le a$$

$$k \le \lfloor \frac{a}{b} \rfloor$$

• 不难发现$k$这个值只和两个集合的大小有关, 因此对于大小为$a$的较大集合, 设该集合有$tot$个，那么对于大小为$b(b < a)$的较小集合, 它会在大小为$a$的集合中出现$tot \times \lfloor \frac{a}{b} \rfloor$个，这些贡献是不合法的，应该减掉

• 在实现程序中为了避免重复减掉同样的贡献，可以用倒序循环实现，具体见程序

• 这题毒瘤卡精度，$pow$会因为精度$WA \ \ 1$个点，可以使用二分 $+ $快速幂代替$pow$函数

以下程序可以处理$n \le 10^{18}$的数据，$d[i]$表示$i$的约数个数（使用线性筛实现，只是为了复习下）, $f[i]$和$g[i]$分别表示大小为$i$的集合的个数，和大小为$i$的集合的期望删除次数，其它数组是线性筛里面的

//ID: LRL52  Date: 2019.10.16
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#include<bits/stdc++.h>
using namespace std;
const int N = 1055, M = 2055; char ss[1 << 21], *A = ss, *B = ss, cc;
inline char gc(){return A == B && (B = (A = ss) + fread(ss, 1, 1 << 21, stdin), A == B) ? EOF : *A++;}
template<class T>inline void rd(T &x){
    int f = 1; x = 0, cc = gc(); while(cc < '0' || cc > '9'){if(cc == '-') f = -1; cc = gc();}
    while(cc >= '0' && cc <= '9'){x = x * 10 + (cc ^ 48); cc = gc();} x *= f;
}
#define int long long
#define double long double
int Pcnt, n;
int d[75], vm[75], prime[75], vm2[75], f[75], h[75];
double g[75], Res;

void Prework(){
    d[1] = 1;
    rep(i, 2, 65){
        if(!vm[i]){
            vm[i] = vm2[i] = i, prime[++Pcnt] = i;
            d[i] = 2;
        }
        rep(j, 1, Pcnt){
            if(prime[j] > vm[i] || prime[j] > 65 / i) break;
            int x = i * prime[j];
            vm[x] = prime[j];
            if(i % prime[j]){
                vm2[x] = prime[j];
                d[x] = d[i] * d[prime[j]];
            }
            else{
                vm2[x] = vm2[i] * prime[j];
                if(x == vm2[x]) d[x] = d[i] + 1;
                else d[x] = d[x / vm2[x]] * d[vm2[x]];
            }
        }
    }
    g[1] = 1.0;
    rep(i, 2, 65) g[i] = g[i - 1] + 1.0 / d[i];
}

int qp(int a, int k){
    int ret = 1; double _a = a;
    Res = 1.0;
    while(k){
        if(k & 1) ret = ret * a, Res = Res * _a;
        a = a * a;
        _a = _a * _a;
        k >>= 1;
    }
    return ret;
}

int calc(int n, int k){
    int l = 1, r = n;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(qp(mid, k) > n || Res > 1e18) r = mid - 1;
        else l = mid + 1;
    }
    return r;
}

#undef int
int main(){
#define int long long
    Prework();
    int Task; rd(Task);
    while(Task--){
        rd(n);
        if(n == 0){
            puts("0.00000000");
            continue;
        }
        double ans = 1.0;
        int up = n;
        rep(i, 1, n){
            //h[i] = pow(n, 1.0 / i);
            h[i] = calc(n, i); //calc n^(1/i)
            --h[i];
            if(h[i] == 0){
                up = i - 1;
                break;
            }
        }
        for(int i = up; i >= 1; --i){
            f[i] = h[i];
            rep(j, i + 1, up)
                f[i] -= (j / i) * f[j];
        }
        rep(i, 1, up) ans += f[i] * g[i];
        printf("%.8Lf\n", ans);
    }
    return 0;
}