题解 UVA11526 【H(n)】

Into_qwq · 2020-06-26 21:21:49 · 题解

刚学完整除分块的蒟蒻来写题解了

不会整除分块看这里

如果看不了(或不想看)也没关系，就在这里讲讲

这题就相当于求这个柿子：\boxed{\sum\limits_{i=1}^{n}\left\lfloor\dfrac{n}{i}\right\rfloor}

很明显O(n)是可以求的，暴力地打上这样的代码：

#include<iostream>
using namespace std;
long long H(int n){
    long long res=0;
    for(int i=1; i<=n; ++i) 
        res+=n/i;
    return res;
}//题目给的函数
int main()
{
    long long n,t;
    cin>>t;
    while(t--){
        cin>>n;
        cout<<H(n)<<endl;
    }
}

不过，提交后，惨烈的TLE了

求的是\left\lfloor\dfrac{n}{i}\right\rfloor

因为是向下取整，所以有些值是一样的

比如n=5时，\left\lfloor\dfrac{n}{3}\right\rfloor和\left\lfloor\dfrac{n}{4}\right\rfloor和\left\lfloor\dfrac{n}{5}\right\rfloor的结果一样

不难发现，这些值是像块状一样分布的qwq

每一个值相同的块的i的最大值一定是\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{i}\right\rfloor}\right\rfloor

可以写出以下代码qwq(附解释):

那么时间复杂度呢？

解：\left\lfloor\dfrac{n}{i}\right\rfloor的取值最多只有2\sqrt n种，理由如下

当1\leqslant i \leqslant \sqrt n时，i的取值有\sqrt n种，则上述式子最多只有\sqrt n种取值 当\sqrt n i \leqslant n时，上述式子取值最多也有\sqrt n种 总共最多有2\sqrt n种取值

由于代码枚举了2\sqrt n次取值，复杂度便为\sqrt n

比暴力好了许多qwq

最后附一遍H函数的代码:

inline LL H(LL n){
    res=0;
    for(LL i=1;i<=n;i=j+1) j=n/(n/i),res+=(j-i+1)*(n/i);
    return res;
}