洛谷P2424 约数和 题解

题目链接：P2424 约数和

题意：

对于一个数 $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)+\dots +f(Y)$的值，你能帮助 Smart 算出这个值吗？

对于 $100\%$ 的数据有 $1\leq X<Y\leq 2\times 10^9$。

设 $f(n) = \sum_{i=1}^{n} g(i)$

其中 $g(i)$ 表示 $i$ 的约数个数和

$$\begin{aligned} f(n) &= \sum_{i=1}^{n} \sum_{j \mid i}^{n} j \end{aligned}$$

变换枚举顺序

$$\sum_{j=1}^{n}j\sum_{i=1}^{n} [j \mid i]$$

不难发现，$\sum_{i=1}^{n} [j \mid i]$ 其实就是求 $1$ 到 $n$ 中包含约束 $j$ 的数的数量，则

$$\sum_{j=1}^{n} j \left\lfloor\frac{n}{j}\right\rfloor$$

也就是

$$f(n) = \sum_{i=1}^{n} i \left\lfloor\frac{n}{i}\right\rfloor$$

然后就是数论分块板子了 awa，答案就是 $f(r)-f(l-1)$

这里前缀和是 $\sum_{i=l}^{r} = \dfrac{1}{2}(l+r)\times(r-l+1)$

有没有一种可能，我居然差点忘了这个前缀和是怎么算的

时间复杂度 $O(\sqrt{n})$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()


int solve(int n)
{
    int res=0;
    for(int l=1,r; l<=n; l=r+1)
    {
        r=n/(n/l);
        res+=(n/l)*(r-l+1)*(l+r)/2;
    }
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int l,r; cin >> l >> r;
    cout << solve(r)-solve(l-1) << '\n';
    return 0;
}