自动搬运

查看原文

来自洛谷，原作者为

	zzlzk **

搬运于2025-08-24 21:37:33，当前版本为作者最后更新于2017-09-22 19:12:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 把$f(x)$用数学方式表示一下就是$f(x)=\sum\limits_{d|x}d$

• 那 $ans=\sum\limits_{i=x}^{y}f(i)=\sum\limits_{i=x}^{y}\sum\limits_{d|i}d$

• 那我们就可以直接枚举然后累加就可以了。

• 但这样的时间复杂度是$O(\sum\limits_{i=x}^{y}\sqrt i)$，会$TLE$

• 所以换一种思路，枚举约数

• 考虑$1-n$中有几个数是 $d$ 的倍数

• 假如$1-n$中存在 $d$ 的倍数，那这个数肯定可以表示为 $k·d(k\in N_+)$

• $k$ 的范围可以再简化一下，$1\leq k·d\leq n\Rightarrow 1 \leq k \leq \lfloor\frac{n}{d}\rfloor$

• 也就是说从$1-n$ 中把 $d$ 的倍数单独拿出来，那就是$d,2d,3d.....\lfloor\frac{n}{d}\rfloor d$

• 所以$1-n$中 $d$ 的倍数的个数就是 $\lfloor\frac{n}{d}\rfloor$

• 求出 $y$ 的个数，再减去 $x-1$ 的个数，也就是$x-y$ 的个数，这个是比较好想的，所以我就不详细说了。

• 这样$\sum\limits_{i=1}^{n}f(i)$就可以表示为$\sum\limits_{i=1}^{n}(\lfloor\frac{n}{i}\rfloor*i)$

• 那$ans=\sum\limits_{i=1}^{y}(\lfloor\frac{y}{i}\rfloor*i)-\sum\limits_{i=1}^{x-1}(\lfloor\frac{x-1}{i}\rfloor*i)$

• 这种做法时间复杂度是$O(y)$，还是会$TLE$

• 再看$\sum\limits_{i=1}^{n}(\lfloor\frac{n}{i}\rfloor*i)$

• 只看$\lfloor\frac{n}{i}\rfloor$，胡乱找个数列出来$\lfloor\frac{n}{i}\rfloor(1\leq i \leq n)$的值

• 以$12$为例，列出来是$12,6,4,3,2,2,1,1,1,1,1,1$ ，第 $i$ 个数表示$\lfloor\frac{n}{i}\rfloor$的值

• 发现这里面有些数是重复的，考虑能不能把这些重复的一次算出来

• 把那些相同的值用区间来表示，那只要求出左右端点$l,r$来就好了

• $l$ 比较好求，观察上面的数列，$l$ 就是上一个$r$加$1$，初始$l=1$

• 那 $r$ 怎么求呢？其实很简单

• $r=n/(n/l)$

• $l$是那个数列的下标，所以 $(n/l)$ 就是约数，那 $r$ 就显然了，如果不知道为什么，那就再看一遍“$1-n$中有几个数是 $d$ 的倍数”。

• $l$ 和$r$ 都知道了， 那答案呢？

• $ans+=$约数*约数的个数

• 约数$=n/l$

• 约数的个数$=\sum\limits_{i=l}^r i$，用等差数列求和公式表示一下就是$(l+r)*(r-l+1)/2$

• 即$ans+=(n/l)*(l+r)*(r-l+1)/2$

• 然后就愉快的AC啦！

比题解不知道短到那里去的代码

#include<cstdio>
using namespace std;
typedef long long ll;

ll sum(int n) {
    if(n<=1) return n;
    ll ans=0;
    for(ll l=1,r;l<=n;l=r+1) {
        r=n/(n/l);
        ans+=(n/l)*(l+r)*(r-l+1)/2;
    }
    return ans;
}

int main() {
    int x,y;
    scanf("%d%d",&x,&y);
    printf("%lld\n",sum(y)-sum(x-1));
    return 0;
}