概述

对于求形如 \(\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);}

相关练习

附AC代码：

#include
    
     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;    }}
    

参考博客：