题解 P1403 【[AHOI2005]约数研究】

· · 题解

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

[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