【题解】P2424 约数和

啊，几个月来第一篇题解，再挣扎两下
\(Description\)

对于一个数X，函数f(X)表示X所有约数的和。例如：f(6)=1+2+3+6=12。对于一个X，Smart可以很快的算出f(X)。现在的问题是，给定两个正整数X,Y(X<Y)，Smart希望尽快地算出f(X)+f(X+1)+……+f(Y)的值，你能帮助Smart算出这个值吗？

\(Sample\) \(Input\)

123 321

\(Sample\) \(Output\)

72543

\(Hint\)

\(n\leqslant 2e9\)

\(Solution\)
我们简单的考虑一下这道题，
约数的和......
哦，我会约数和定理！
时间复杂度 \(\mathcal O(n^2logn)\)
我们考虑不能直接求每个数的约数和但是我们可以考虑每个数的贡献。

比如对于 \(i\) 我们考虑他作为约数对答案的贡献，假设我们要做到 \(n\) 。
那么有 \(\lfloor\frac{n}{i}\rfloor\) 个约数每个约数是 \(i\) 那么 \(i\) 对 \(f(n)\) 的贡献是\(\lfloor \frac{n}{i}\rfloor * i\)
所以我们可以得到一个快速求 \(f(n)\) 的办法：
\(f(n)=\sum_{i=1}^{n} \lfloor \frac{n}{i}\rfloor * i\)
时间复杂度：\(\mathcal O(n)\)
好像还是过不了(那讲个鬼啊
但是这提示了正解，我们看到除法在这样一个式子里我们是不是可以考虑除法分块呢？

把商相同的直接一次算完。
我们把商相同的区间的左右端点叫做 \(l,r\)
我们现在只要求 \(l,r\) 就可以
显然 \(l=r+1\)
\(\frac{n}{l}\) 是商,右端点就是 \(n/\frac{n}{l}\) 。
之后只要把当前这个商提出来再等差数列求个和
\(f(n)=\sum_{i=1}^{n} (r-l+1)*(l+r)/2*(n/l)\)
时间复杂度 \(\mathcal O(\sqrt n)\)

#include <bits/stdc++.h>
using namespace std;

#define int long long

inline int sum(int n){
    int ans=0;
    for(int L=1,R=0;L<=n;L=R+1){
        R=n/(n/L);
        ans+=(L+R)*(R-L+1)/2*(n/L);
    }
    return ans;
}

signed main(){
    int l,r;
    scanf("%lld%lld",&l,&r);
    printf("%lld\n",sum(r)-sum(l-1));
    return 0;
}

【题解】P2424 约数和

原文：https://www.cnblogs.com/JCNL666/p/11734452.html