HDU 2011 多項式求和：交替調和級數部分和

題目大意

計算 S(m) = Σ_{i=1..m} (-1)^{i+1} / i，輸出保留兩位小數。多測試用例。

代碼實現

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main()
{
    int n; cin >> n;
    while (n--) {
        int m; cin >> m;
        double sum = 0.0;
        for (double i = 0; i < m; ++i)
            sum += (1.0 / (i + 1)) * pow(-1.0, i);
        cout << fixed << setprecision(2) << sum << endl;
    }
    return 0;
}

關鍵點

• pow(-1.0, i) 產生交替符號（i 為 double 避免整數冪溢出/精度問題）。
• fixed + setprecision(2) 強制輸出兩位小數（四捨五入）。
• 時間復雜度 O(m) 每測試用例，m 範圍未給出但通常 ≤ 10⁴，直接循環足夠。

優化方向

1. 避免 pow：用符號變量 int sign = 1; sign = -sign; 翻轉，更快且精確。
2. 預計算前綴和：若測試用例多且 m 最大值可知，預計算 prefix[m] 實現 O(1) 查詢。
3. 精度考慮：大 m 時交替級數收斂緩慢，double 足夠兩位小數精度；更高精度可用 long double 或 Kahan 求和。

優化版片段

double sum = 0.0;
int sign = 1;
for (int i = 1; i <= m; ++i) {
    sum += sign * 1.0 / i;
    sign = -sign;
}