题目描述 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)的值。
样例输入 Sample Input
2 4
样例输出 Sample Output
14
数据范围及提示 Data Size & Hint
对于20%的数据有1≤X＜Y≤10^5。
对于60%的数据有1≤X＜Y≤1*10^7。
对于100%的数据有1≤X＜Y≤2*10^9。
思路：
这道题代码很简单，主要难点是推公式，我们先可以先推出： ans = ∑⌊n/i⌋*i （1<=i<=n,向下取整），解释下这个公式，我们是取1-n的约数和，那么 n/i向下取整也就是1-n中所有可以整除i的数的个数，然后再乘上i就是i这个约数对答案的贡献，i从1-n跑一边便可以算出答案，但是这样会超时的，那么我们需要优化下这个公式，因为是向下去整的那么肯定会有一些连续的数除i后向下取整得到的值一样，我们可以求出这些值的左右边界，将其归为一块，因为⌊n/i⌋（1<=i<=n,）的值一定递增的等差数列，那么我们求出每一个块的左右边界，直接套用等差数列的求和公式，(a1+an)*n/2, 带入l,r就是： (l+r)*(r-l+1)/2，这样就求的了个数之后再乘上权值就好了。
#include<bits/stdc++.h>
using namespace std;
#define ll long long ll solve(ll x){
if(x == ||x == ) return x;
ll l = ,r = ,ans = ; //左右边界
while(l <= x){
r = x/(x/l);
ans += (x/l)*(l+r)*(r-l+)/;
l = r+;
}
return ans;
} int main()
{
ll x,y;
scanf("%lld%lld",&x,&y);
cout<<solve(y) - solve(x-)<<endl;
}
实现代码：