求f(n)=[n/1]+[n/2]+---+[n/n]的值 简单杂题

时间:2023-03-08 22:33:15
求f(n)=[n/1]+[n/2]+---+[n/n]的值 简单杂题

这种小题首先根据

n/1+n/2+n/3+--+n/n=nlogn+欧拉常数r 可以知道 1e12的范围也不会爆longlong,不需要写高精度(到现在都不会写)

再根据数据范围可知O(n)级别的暴力不可过,所以考虑到了sqrt(n)的算法

当i<=sqrt(n)时,最多只有sqrt(n)个不同的数,结果值一定小于sqrt(n);

当sqrt(n)<i时,[n/i]<sqrt(n),故一定有小于sqrt(n)种结果

最后顺序遍历,但统计时遇到下相同n/i值直接累加并跳过

1    2    3    4    5    6    7    8    9   10

10  5    3    2    2    1    1    1    1    1

我们发现,对于一个数i,例如i==4

她的贡献值 d=n/i=10/4=2,得到的有榆树,那么d值变小

与之对应的,那么n/d得到的实际上是该同值数字的上界,下一次指针直接跳入上界的下一个值即可

#include<bits/stdc++.h>
#define LL long long
LL n,ans,d;
int main(){
freopen("imouto.in","r",stdin);
freopen("imouto.out","w",stdout);
scanf("%lld",&n);
for(LL i=;i<=n;i=(n/d)+){
d=n/i;
ans+=1LL*d*(n/d-i+);}
printf("%lld",ans);return ;
}