题解 UVA11526 【H(n)】

· · 题解

\text{Link}

## 题意 求 ```cpp long long H(int n){ long long res=0; for( int i = 1; i <= n; i=i+1 ){ res = (res + n/i); } return res; } ``` 的值。 多组数据。 $1\le T\le 10^3,1\le n<2^{31}

思路

很明显，直接模拟题目给出的函数会 TLE。

我们理解一下题目给的代码，其实就是求

\sum\limits_{i=1}^n\left\lfloor\dfrac{n}{i}\right\rfloor

此时，我们需要引入算法：整除分块（又称数论分块、除法分块）。此算法可以快速求出形如

\sum\limits_{i=1}^nf(\left\lfloor\dfrac{n}{i}\right\rfloor)

的式子，在数论题目中有着广泛的用途。

对于一些情况，一段数满足

\left\lfloor\dfrac{n}{l}\right\rfloor = \left\lfloor\dfrac{n}{l+1}\right\rfloor = \left\lfloor\dfrac{n}{l+2}\right\rfloor = ... = \left\lfloor\dfrac{n}{l+m}\right\rfloor = ... = \left\lfloor\dfrac{n}{r-1}\right\rfloor = \left\lfloor\dfrac{n}{r}\right\rfloor

这时候我们把这个值重复地加了几遍，浪费了时间。

我们可由向下取整的性质得：

\left\lfloor\dfrac{n}{l}\right\rfloor\leqslant\dfrac{n}{r}<\left\lfloor\dfrac{n}{l}\right\rfloor+1

化简得

r\leqslant\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{l}\right\rfloor}\right\rfloor r_{max}=\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{l}\right\rfloor}\right\rfloor

所以对于上面这 r-l+1 个相同的数它们的和为

(\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{l}\right\rfloor}\right\rfloor-l+1)×\left\lfloor\dfrac{n}{l}\right\rfloor

分析一下时间复杂度，发现时间复杂度即对于 n，所有的 \lfloor\frac n i\rfloor 的取值数量，可以知道，\lfloor\frac n i\rfloor 可以取得 1,2,\cdot\cdot\cdot,\sqrt n,\lfloor\frac n {\sqrt n}\rfloor,\lfloor\frac n {\sqrt n-1}\rfloor,\cdot\cdot\cdot,n 这 O(\sqrt n) 种取值，即时间复杂度为 O(T\sqrt n)。

注意此题轻微卡常。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){

}
inline int h(int n){
    if(!n){
        return 0;
    }
    int res=0,j;
    for(register int i=1;i<=n;i=j+1){
        j=n/(n/i);
        res+=(j-i+1)*(n/i);
    }
    return res;
}
signed main(){
    int t,n;
    t=read();
    while(t--){
        n=read();
        printf("%lld\n",h(n));
    }
    return 0;
}

再见 qwq~