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)的值。
输入输出样例
2 4
14
123 321
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了,原因未知。。。