# Nemlit 的博客

By a konjac

### 题解 P5589 【小猪佩奇玩游戏】

posted on 2019-10-16 17:21:28 | under 题解 |

## $Code:$

#include<bits/stdc++.h>
using namespace std;
#define rep(i, s, t) for(int i = s; i <= t; ++ i)
#define drep(i, s, t) for(int i = t; i >= s; -- i)
#define maxn 100005
int p[maxn], f[maxn], n, m;
double g[maxn], ans;
bool check(int a, int b, int n) {
long long pax = a;
for(; b; b --, pax = pax * a) if(pax > 1ll * n) return 1;
return 0;
}
int get(int i, int n) {
int l = 1, r = n, ans = n;
while(l <= r) {
int mid = (l + r) >> 1;
if(check(mid, i, n)) r = mid - 1, ans = mid;
else l = mid + 1;
}
return ans - check(ans, i, n);
}
int d(int x) {
int ans = 1;
rep(i, 2, 30) {
if(x % i) continue;
int tot = 0;
while(x % i == 0) ++ tot, x /= i;
ans *= (tot + 1);
}
return ans;
}
void init() {
g[1] = 1.0;
rep(i, 2, 30) g[i] = g[i - 1] + 1.0 / d(i);
}
int main() {
init(), scanf("%d", &m);
while(m --) {
scanf("%d", &n), ans = 1, p[31] = 1;
rep(i, 1, 30) p[i] = get(i, n);
rep(i, 1, 30) f[i] = p[i] - p[i + 1];
drep(i, 1, 30) rep(j, 2, 30) f[i / j] -= f[i];
rep(i, 1, 30) ans += g[i] * f[i];
printf("%.10lf\n", ans);
}
return 0;
}