https://www.luogu.org/problem/show?pid=2424
题目背景
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。
#include <cstdio> #define LL long long
inline void read(LL &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
}
LL x,y,ans; int Presist()
{
// freopen("A.in","r",stdin);
// freopen("A.out","w",stdout);
read(x),read(y);
if(x>y) {LL tmp=x;x=y;y=tmp;} x--;
for(LL i=;i<=y; ++i)
ans+=i*(y/i)-i*(x/i);
printf("%I64d",ans);
return ;
} int Aptal=Presist();
int main(int argc,char *argv[]){;}
60，暴力算每个约数和
可以发现，有些约数的个数是相同的，考虑将它们一起算，
枚举相同约数个数的左边界，右边界=i/(i/l)，等差数列Sn=（s1+sn）>>1；
#include <cstdio> #define LL long long
inline void read(LL &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
}
LL x,y,ans;
inline LL sum(LL a)
{
if(a<) return ;
LL ret=,l=,r=;
for(; l<=a; l=r+)
{
r=a/(a/l);
ret+=(r-l+)*(a/l)*(l+r)>>;
}
return ret;
} int Presist()
{
// freopen("A.in","r",stdin);
// freopen("A.out","w",stdout);
read(x),read(y);
if(x>y) {LL tmp=x;x=y;y=tmp;}
printf("%lld",sum(y)-sum(x-));
return ;
} int Aptal=Presist();
int main(int argc,char *argv[]){;}