洛谷P2424 约数和

题意

$$f(x)=\sum_{i \mid x} i$$
求
$$f(x)+ f(x+1)+ \dots +f(y)$$
数据范围：$1 \le x<y \le 2 \times 10^9$

题解

算法：数论分块
记
$$F(x)=\sum_{i=1}^x f(i)$$
可用前缀和，题目所求即为
$$F(y)-F(x-1)$$
现在计算$F(x)$，对于一个约数$i$，在$[1,x]$中共出现$\lfloor \frac{x}{i} \rfloor$次，因此它对答案的贡献即为$i \cdot \lfloor \frac{x}{i} \rfloor$
由于$[1,x]$中每一个数皆可作为约数，答案为
$$\sum_{i=1}^x i \cdot \lfloor \frac{x}{i} \rfloor$$
而对它可以进行数论分块

代码：

#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
int x,y;
inline int calc(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(){
    scanf("%lld%lld",&x,&y);
    printf("%lld",calc(y)-calc(x-1));
    return 0;
}