自动搬运

查看原文

来自洛谷，原作者为

	Kelin 这个家伙太菜，没什么可以留下的

搬运于2025-08-24 21:24:41，当前版本为作者最后更新于2017-08-08 12:26:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实这题没那么难优化什么的

$[1,n]$里约数有$i$的个数是$\lfloor\frac ni\rfloor$

所以$ans=\sum_{i=1}^n\lfloor\frac ni\rfloor$然后我们打表发现

有很多$\lfloor\frac ni\rfloor$都是一样的 对于这些一样的数我们每次算一次 似乎很浪费时间

所以我们每次$i$跳到$\lfloor\frac nj\rfloor=\lfloor\frac ni\rfloor+1$这样的$j$上 对于中间一样的数一次性算掉

这样的复杂度又是多少呢?打表测试一下就好了 复杂度$O(2\sqrt n)$//其实这道题数据范围可以出到$10^{14}$的 手动滑稽

#include<cstdio>
int n,ans;
int main(){
    scanf("%d",&n);
    for(int i=1,j;i<=n;i=j+1){
        j=n/(n/i);
        ans+=(n/i)*(j-i+1);
    }
    printf("%d",ans);
return 0;
}

$upd:2018.3.30$

突然发现好多评论哇$qwq$

告诉泥萌还有$O(n^{\frac13}\log n)$的做法呢

详见$[Spoj26073]DIVCNT1$