洛古-p2424除数和

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。

1 #include <cstdio> 2 3 #define LL long long 4 inline void read(LL &x) 5 { 6 x=0; register char ch=getchar(); 7 for(; ch>'9'||ch<'0'; ) ch=getchar(); 8 for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0'; 9 } 10 LL x,y,ans; 11 12 int Presist() 13 { 14 // freopen('A.in','r',stdin); 15 // freopen('A.out','w',stdout); 16 read(x),read(y); 17 if(x>y) {LL tmp=x;x=y;y=tmp;} x--; 18 for(LL i=1;i<=y; ++i) 19 ans+=i*(y/i)-i*(x/i); 20 printf('%I64d',ans); 21 return 0; 22 } 23 24 int Aptal=Presist(); 25 int main(int argc,char *argv[]){;}

60，暴力算每个约数和

可以发现，有些约数的个数是相同的，考虑将它们一起算，

枚举相同约数个数的左边界，右边界=i/(i/l)，等差数列Sn=（s1+sn）>>1；

1 #include <cstdio> 2 3 #define LL long long 4 inline void read(LL &x) 5 { 6 x=0; register char ch=getchar(); 7 for(; ch>'9'||ch<'0'; ) ch=getchar(); 8 for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0'; 9 } 10 LL x,y,ans; 11 inline LL sum(LL a) 12 { 13 if(a<2) return 0; 14 LL ret=0,l=1,r=0; 15 for(; l<=a; l=r+1) 16 { 17 r=a/(a/l); 18 ret+=(r-l+1)*(a/l)*(l+r)>>1; 19 } 20 return ret; 21 } 22 23 int Presist() 24 { 25 // freopen('A.in','r',stdin); 26 // freopen('A.out','w',stdout); 27 read(x),read(y); 28 if(x>y) {LL tmp=x;x=y;y=tmp;} 29 printf('%lld',sum(y)-sum(x-1)); 30 return 0; 31 } 32 33 int Aptal=Presist(); 34 int main(int argc,char *argv[]){;}

——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。