洛谷—— P2424 约数和

https://www.luogu.org/problem/show?pid=2424

题目背景

Smart最近沉迷于对约数的研究中。

题目描述

对于一个数X，函数fX)表示X所有约数的和。例如：f6)=1+2+3+6=12。对于一个X，Smart可以很快的算出fX)。现在的问题是，给定两个正整数X,YX<Y)，Smart希望尽快地算出fX)+fX+1)+……+fY)的值，你能帮助Smart算出这个值吗？

输入输出格式

输入格式：

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

输出格式：

输出只有一行，为fX)+fX+1)+……+fY)的值。

输入输出样例

输入样例#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 readLL &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     readx),ready);
17     ifx>y) {LL tmp=x;x=y;y=tmp;} x--;
18     forLL 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 mainint argc,char *argv[]){;}

60，暴力算每个约数和

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

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

 1 #include <cstdio>
 2 
 3 #define LL long long
 4 inline void readLL &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 sumLL a)
12 {
13     ifa<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     readx),ready);
28     ifx>y) {LL tmp=x;x=y;y=tmp;}
29     printf"%lld",sumy)-sumx-1));
30     return 0;
31 }
32 
33 int Aptal=Presist);
34 int mainint argc,char *argv[]){;}

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