UVA11526 H(n) 题解

· · 题解

准备

求和符号：

\sum\limits_{i=1}^na_i=a_1+a_2+...+a_n

向下取整：

\left\lfloor\dfrac{1}{2}\right\rfloor=0,\left\lfloor-\dfrac{1}{2}\right\rfloor=-1

向上取整：

\left\lceil\dfrac{1}{2}\right\rceil=1,\left\lceil-\dfrac{1}{2}\right\rceil=0

旅途的开始

当我问你一个这样的问题：

\sum\limits_{i=1}^{10}{\left\lfloor\tfrac{10}{i}\right\rfloor}=?

列个表格试试：

\boxed{\left\lfloor\dfrac{10}{1}\right\rfloor=10},\boxed{\left\lfloor\dfrac{10}{2}\right\rfloor=5},\boxed{\left\lfloor\dfrac{10}{3}\right\rfloor=3},\boxed{\left\lfloor\dfrac{10}{4}\right\rfloor=2},\boxed{\left\lfloor\dfrac{10}{5}\right\rfloor=2}, \boxed{\left\lfloor\dfrac{10}{6}\right\rfloor=1},\boxed{\left\lfloor\dfrac{10}{7}\right\rfloor=1},\boxed{\left\lfloor\dfrac{10}{8}\right\rfloor=1},\boxed{\left\lfloor\dfrac{10}{9}\right\rfloor=1},\boxed{\left\lfloor\dfrac{10}{10}\right\rfloor=1}

如果我们把这些一个一个加起来，那会很慢，那该怎么办呢？

于是，观察表格可以发现，有一些答案和后面的答案一样（一段区间内一样）

那么我们就可以把 1\sim 10 分个段：分别是 1,2,3,4\sim 5,6\sim 10

这样我们就只用计算 5 次 \left\lfloor\dfrac{10}{i}\right\rfloor 就行了。

那么，问题来了，如何确定答案相同的区间呢？

公式推导

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

（注：n 为正整数）

假设我们已知某一个分块的左端点 l，要求解出该分块的右端点 r。设该分块的数值为 k，对于该分块中的每个数 i，有 k=\left\lfloor\dfrac{n}{i}\right\rfloor=\left\lfloor\dfrac{n}{l}\right\rfloor，即 ik\leq n，想一想就可以知道当 i=r 时，也就是 \max(rk)\leq n 为最大值。

所以，就可以发现：

r=\left\lfloor\dfrac{n}{k}\right\rfloor

又因为：

k=\left\lfloor\dfrac{n}{l}\right\rfloor

所以：

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

则，代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10^48);
}
int t,n;
signed main(){
    t=read();
    while(t--){
        n=read();
        int ans=0;
        for(int l=1,r;l<=n;l=r+1){
            r=n/(n/l);
            ans+=(r-l+1)*(n/l);
        }
        print(ans),puts("");
    }
    return 0;
}
$$\left\lfloor \frac{n}{l}\right\rfloor=\left\lfloor\frac{n}{r}\right\rfloor$$ 证 $r=\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor$。 证明： $$\left\lfloor\frac{n}{l}\right\rfloor\leq\frac{n}{l}$$ $$l=\left\lfloor\frac{n}{\frac{n}{l}}\right\rfloor \leq \left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor$$ $$l_{\max}=\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor=r$$ $\Box