洛谷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;
}