LightOJ - 1234 Harmonic Number（调和级数分块打表）

传送门

---

题目大意

求$f(n)={\sum }_{i=1}^n\frac{1}{i}$

解题思路

方法一

看到这个东西异常熟悉，不就是高数讲过的调和级数吗，但是忘记通项公式是什么了，去百度，有的地方说函数的极限是$f(n)=ln(n+1)+\gamma$，但是实际上这个是不精确的，正确的极限应该是$ln(n)+\gamma +\frac{1}{2n}$，测试时在$1e^6$以后的误差就小于了$1e^{-8}$，所以只需要处理出前$1e^6$项

方法二

说实话还真的没有想到分块打表，看到题解提到这个关键词才恍然大悟，因为每一项的贡献对其他项互不影响，而数组开不了那么大，但是时间够，因此考虑分块打表，那么只需求出前缀和，每$100$项压缩成一个块，这样只需要$1e^6$大小的数组，预处理之后，每次查询最后计算一百次就能得到结果。

// // Created by Happig on 2020/10/21 // #include <bits/stdc++.h> #include <unordered_map> #include <unordered_set> using namespace std; #define fi first #define se second #define pb push_back #define ins insert #define Vector Point #define ENDL "\n" #define lowbit(x) (x&(-x)) #define mkp(x, y) make_pair(x,y) #define mem(a, x) memset(a,x,sizeof a); typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; const double eps = 1e-8; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double dinf = 1e300; const ll INF = 1e18; const int Mod = 1e9 + 7; const int maxn = 1e8; const double y = 0.5772156649015328606065120; const int sz = 100; double a[1000010]; void init() { double ans = 0; for (int i = 1; i < maxn; i++) { ans += 1.0 / i; a[i] = ans; } //printf("%.8lf", a[1000000] - log(1000000) - y - 1.0 / (2 * 1000000)); } double solve(int n) { if (n < maxn) return a[n]; return log(n) + y + 1.0 / (2 * n); } void table() { double ans = 0.0; a[0] = 0.0; for (int i = 1; i <= maxn; i++) { ans += 1.0 / i; if (i % sz == 0) { a[i / sz] = ans; } } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); //ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T, kase = 0, n; table(); scanf("%d", &T); while (T--) { scanf("%d", &n); int x = n / sz; double ans = a[x]; for (int i = x * sz + 1; i <= n; i++) { ans += 1.0 / i; } printf("Case %d: %.8lf\n", ++kase, ans); // if (n < maxn) printf("Case %d: %.8lf\n", ++kase, a[n]); // else printf("Case %d: %.8lf\n", ++kase, log(n) + y + 1.0 / (2 * n)); } return 0; }