codevs 2606 约数和问题

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)的值。

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

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

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

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

　　下面贴代码：

 1 #include<cstdio>
 2 #include<cmath>
 3 
 4 using namespace std;
 5 typedef long long llg;
 6 
 7 llg work(int x){
 8     llg ans=0,la=x,gi=(llg)sqrt(x);
 9     for(llg i=1,g;i<=gi;i++){
10         g=x/i;
11         ans+=i*g+(g+1+la)*(la-g)/2*(i-1);
12         la=x/i;
13     }
14     ans+=(gi+1+la)*(la-gi)/2*gi;
15     return ans;
16 }
17 
18 int main(){
19     int l,r;
20     scanf("%d %d",&l,&r);
21     printf("%lld",work(r)-work(l-1));
22 }