http://codevs.cn/problem/2606/

https://luogu.lohu.info/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。

记住一点:求[l,r],先想想前缀和[1,r]-[1,l-1]

一开始想到的:

60分TLE

[1,n]数i的出现次数为n/i

就这个还是想了好久,写出来才发现的

智商啊!!!!!

1=1

2=1+2

3=1+    3

4=1+2+    4

5=1+           5

6=1+2+3+      6

#include<cstdio>
using namespace std;
int x,y;
long long ans;
int main()
{
scanf("%d%d",&x,&y);
for(int i=;i<=x-;i++) ans-=i*((x-)/i);
for(int i=;i<=y;i++) ans+=i*(y/i);
printf("%lld",ans);
}

AC做法:

除法分块

以12为例:

i               1    2    3   4  5  6  7  8  9  10  11  12

出现次数    12   6   4   3  2  2   1  1  1  1    1    1

可以发现数i在[1,n]中的出现次数相同的数是挨在一块的

由于挨着,所以它又是一个等差数列

所以可以出现次数相同的作为一块一起算

设每一块所在区间为[L,R]

可以枚举L,那么R=n/(n/L)

(不要问怎么想出来的,学长说脑子,O| ̄|_  ,需要扶助的智商啊啊啊啊o(≧口≦)o)

所以这一块的ans=每个数的出现次数(n/L)*这一块所包含的的的数的总和

其中这一块所包含的数的总和,用等差数列求和公式 (a1+an)*n/2,可得

=(L+R)*(R-L+1)/2

#include<cstdio>
using namespace std;
long long x,y;
long long work(long long n)
{
long long ans=,i=,j;
while(i<=n)
{
j=n/(n/i);
ans+=(n/i)*(i+j)*(j-i+)/;
i=j+;
}
return ans;
}
int main()
{
scanf("%lld%lld",&x,&y);
printf("%lld",work(y)-work(x-));
}

注意要用long long,因为ans+=后面那一串可能会爆int,70分

于是我就改成了ans+=1ll*(1ll*n/1ll*i)*(1ll*i+1ll*j)*(1ll*j-1ll*i+1)/2;

然后就0了,原因未知。。。

05-11 15:13