codevs 2606 约数和问题

题目描述 Description

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算出这个值吗？

输入描述 Input Description

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

输出描述 Output Description

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

 

　　首先，对于区间$[l,r]$显然可以拆成$[1,r]$与$[1,l-1]$的差。然后，由于求的是区间的因数和，那么一个显然的想法就是枚举约数$x$，若区间内有$y$个数有$x$这个约数，那么$ans$就要加上$x*y$，对于区间$[1,n]$也就是$lfloor n/i floor *i$。

　　这样一来，我们就把问题转化成了求这个式子的值：

$$sum_{i=1}^{n}lfloor n/i floor * i$$

　　由于$lfloor n/i floor$只有$sqrt{n}$种取值，就可以对于$i le sqrt{n}$的暴力算一下$lfloor n/i floor * i$，同时算一下$lfloor n/x floor =i$的$x$的范围，统计一下即可。

　　下面贴代码：

#include<cstdio>
#include<cmath>

using namespace std;
typedef long long llg;

llg work(int x){
    llg ans=0,la=x,gi=(llg)sqrt(x);
    for(llg i=1,g;i<=gi;i++){
        g=x/i;
        ans+=i*g+(g+1+la)*(la-g)/2*(i-1);
        la=x/i;
    }
    ans+=(gi+1+la)*(la-gi)/2*gi;
    return ans;
}

int main(){
    int l,r;
    scanf("%d %d",&l,&r);
    printf("%lld",work(r)-work(l-1));
}