11526 H(n)

題目翻譯

定義

H(n) = floor(n/1) + floor(n/2) + ... + floor(n/n)

給你多筆 n，請輸出每筆的 H(n)。

輸入

第一行是測資數量 T。
接下來 T 行每行有一個整數 n（可能是負數或極大整數，需使用 64 位元整數）。

輸出

對於每個 n，輸出一行 H(n) 的計算結果。

解題思路

直接從 1 加到 n 會太慢，重點在於：floor(n/i) 的值在一段區間內會相同。

這份程式用遞迴分治壓縮計算：

1. dc(l, r) 代表處理 i 在 [l, r] 的總和。
2. 若 l == r，直接加上 n / l。
3. 取 mid 後，若 n / mid == n / r，表示 [mid, r] 商都一樣，可一次加上 (r - mid + 1) * (n / mid)，只遞迴左半。
4. 否則把區間拆開繼續分治。

透過批次累加相同商值的區段，能大幅減少實際計算次數，順利通過時限。

程式碼

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define idonthavegirlfriend ios::sync_with_stdio(0), cin.tie(0);
#define pb push_back
#define yn(a) (a ? "Yes\n" : "No\n")
// #include <atcoder/fenwicktree>
// #include <atcoder/dsu>
// using namespace atcoder
// author:Jackis666
int ans = 0;
int n;
void dc(int l, int r) {
    if (l > r) return;
    if (l == r) {
        ans += n / l;
        return;
    }
    int mid = (l + r) / 2;
    if (n / mid == n / r) {
        ans += (r - mid + 1) * (n / mid);
        dc(l, mid - 1);
    } else {
        dc(l, mid - 1);
        dc(mid, mid);
        dc(mid + 1, r);
    }
}
signed main() {
    idonthavegirlfriend
    int t;
    cin >> t;
    while (t--) {
        ans = 0;
        cin >> n;
        dc(1, n);
        cout << ans << "\n";
    }
}

另一個方法是透過觀察
計算 $\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor$ 實際上等同於計算在第一象限中
滿足 $xy \le n$ 的正整數格子點 $(x,y)$ 的總數
當 n = 6 時

y \ x	1	2	3	4	5	6
6	[X]	.	.	.	.	.
5	[X]	.	.	.	.	.
4	[X]	.	.	.	.	.
3	[X]	[X]	.	.	.	.
2	[O]	[O]	[Y]	.	.	.
1	[O]	[O]	[Y]	[Y]	[Y]	[Y]

把表畫出來可以發現，是對直線 $y=x$ 對稱的
因為左右對稱，這意味著只要計算到 $sqrt(n)$​，剩下的另一半可以靠翻轉得到
所以把左側的數量乘二，就涵蓋了大部分的區域
但是左下角那個邊長為 $sqrt(n)$​（即 2×2）的小正方形區域 [O] 被重複算了兩次
扣掉那塊重複算的正方形（n​×n​），剩下的就是精確的總數了

//author: Piau
#include <bits/stdc++.h>
using namespace std;

#define WA() cin.tie(0)->sync_with_stdio(0)
#define int long long

int H(int n) {
    int res = 0, sn = sqrt(n);
    for (int i = 1; i <= sn; i++) res += n/i;
    return 2*res - sn*sn;
}

signed main() { WA();
    int t; for (cin >> t; t--;) {
        int n; cin >> n;
        cout << H(n) << '\n';
    }
}