LightOJ 1234 Harmonic Number：調和級數部分和快速計算

題目

計算 H(n) = 1 + 1/2 + ... + 1/n，n ≤ 10^8，多組測試，輸出保留 10 位小數。

解法：預計算 + 歐拉-馬歇羅尼常數近似

調和級數發散，但增長緩慢。對於 n ≤ 10^6 直接預計算前綴和；n > 10^6 使用近似公式：

H(n) ≈ ln(n + 0.5) + γ

其中 γ ≈ 0.57721566490153286060651209 為歐拉常數。+0.5 修正項顯著提高精度，滿足 1e-10 要求。

代碼

#include <cstdio>
#include <cmath>
const int MAXN = 1000000;
const double GAMMA = 0.57721566490153286060651209;
double H[MAXN+1];

int main() {
    H[0] = 0;
    for (int i = 1; i <= MAXN; ++i) H[i] = H[i-1] + 1.0/i;
    int T, cas = 1; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        double ans = (n <= MAXN) ? H[n] : log(n + 0.5) + GAMMA;
        printf("Case %d: %.10f\n", cas++, ans);
    }
    return 0;
}

複雜度

預處理 O(MAXN)，查詢 O(1)，空間 O(MAXN)。近似公式誤差 O(1/n^2)，對大 n 極其精確。