题解 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$](https://www.luogu.org/problemnew/show/SP26073)