这种小题首先根据
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 ;
}