整除分块思想

概述

对于求形如 \(\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor\) 的值，就需要用到整除分块，否则当n很大时就会超时。在普通的一个一个的计算时可以发现很多\(\lfloor\frac{n}{i}\rfloor\)的值成块状分布，最终的到的规律是发现对于每一个值相同的块，它的最后一个数就是n/(n/i)

代码

for(int l=1,r;l<=n;l=r+1)
{
    r=n/(n/l);
    ans+=(r-l+1)*(n/l);
}

相关练习

H(n) UVA - 11526

附AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int T;
LL n;
LL H(int a)
{
    LL ans = 0;
    for(LL l = 1, r; l <= a; l = r + 1)
    {
        r = a / (a / l);
        ans += (r - l + 1)*(n / l);
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    cin >> T;
    while(T--)
    {
        cin >> n;
        cout << H(n) << endl;
    }

}