P2424 约数和

题目背景

Smart最近沉迷于对约数的研究中。

题目描述

对于一个数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算出这个值吗？

输入输出格式

输入格式：

 

输入文件仅一行，两个正整数X和Y（X<Y），表示需要计算f(X)+f(X+1)+……+f(Y)。

 

输出格式：

 

输出只有一行，为f(X)+f(X+1)+……+f(Y)的值。

 

输入输出样例

输入样例#1： 

2 4

输出样例#1： 

14

输入样例#2： 

123 321

输出样例#2： 

72543

说明

对于20%的数据有1≤X＜Y≤105。

对于60%的数据有1≤X＜Y≤1*107。

对于100%的数据有1≤X＜Y≤2*109。

Solution：

　　本题数论分块。。。

　　首先很容易想到前缀和的思想，求$x ightarrow y$的约数和，也就等于求$1 ightarrow y$的约数和减去$1 ightarrow x-1$的约数和。

　　那么在$1 ightarrow n$中会出现的约数显然有$n$个（即$1 ightarrow n$每个数都可作为约数），则对于约数$d,;din[1,n]$，其对约数和的贡献为$d imes lfloor{n/d} floor$，即$ans=sumlimits_{i=1}^{n}{(i imeslfloor{n/i} floor)}$。

　　然后对于$i imeslfloor{n/i} floor$直接数论分块套上等差数列求和就好了。

代码：

#include<bits/stdc++.h>
#define il inline
#define ll long long
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)>(b)?(b):(a))
using namespace std;
ll x,y;

il ll solve(ll x){
    if(x==1)return 0;
    ll ans=0,p=0;
    for(ll i=1;i<=x;i=p+1){
        p=x/(x/i);
        ans+=(x/i)*(i+p)*(p-i+1)/2;
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin>>x>>y;
    cout<<solve(y)-solve(x-1);
    return 0;
}