P3766 核心密码B

zesqwq · 2023-08-08 20:41:09 · 题解

考虑到我完全不会数学。

我们考虑对于 a^b，对每个 b 单独算贡献。

如果 b \ge 3，我们可以使用 O(\sqrt[b]V) 的做法，这是简单的，可以对询问排序后双指针做，也可以预处理，反正不重要。

对于 b = 2，我们可以先暴力高出 a \le 10^7 时的贡献，对于更大的，我们可以取一个近似，把 \dfrac {1} {x^2} 变为 \dfrac{\dfrac{1}{(x-1)x}+\dfrac{1}{x(x+1)}}2，上面两个是可以直接裂项做的，该近似精度没有积分的近似优秀，但仍然可以通过此题并且获得最优解。

struct Query{
    ll k;
    int id;
    inline bool operator<(Query b) { return k < b.k; }
} q[Q];
__int128 qpw(__int128 a, ll b) {
    __int128 ans = 1;
    while (b) {
        if (b & 1) ans = ans * a;
        a = a * a, b >>= 1;
    }
    return ans;
}
long double ans[Q];
int T;
inline void solve(int x) {
    int r = 2;
    __int128 qr = qpw(r, x);
    long double now = 0;
    for (int i = 1; i <= T; i++) {
        while (qr <= q[i].k) now += (long double)1.0 / qr, ++r, qr = qpw(r, x);
        ans[q[i].id] += now;
    }
}
inline long double calc(ll x) {
    long double ta = 1.0 / 10000000 - (long double)(1.0) / (x + 1);
    long double tb = 1.0 / (10000000 - 1) - (long double)(1.0) / x;
    return (ta + tb) / 2;
}
int main() {
    read(T);
    for (int i = 1; i <= T; i++) read(q[i].k), q[i].id = i;
    sort(q + 1, q + T + 1);
    for (int i = 3; i <= 60 ;i++) solve(i);
    for (int i = 1; i <= T; i++)
        if (q[i].k > 100000000000000) {
            int tmp = sqrtl(q[i].k);
            ans[q[i].id] += calc(tmp);
            q[i].k = 100000000000000;
        }
    solve(2);
    for (int i = 1; i <= T; i++) printf("%.15Lf\n", ans[i]);
    return 0;
}