求问一个复杂度
  • 板块学术版
  • 楼主aish
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/7/25 15:23
  • 上次更新2023/11/3 07:43:38
查看原帖
求问一个复杂度
939357
aish楼主2023/7/25 15:23

数论分块套数论分块的复杂度是多少？

例如求：

f(n)=∑i=1ng(⌊ni⌋)f(n) = \sum_{i = 1}^n g(\lfloor \frac ni \rfloor) g(n)=∑i=1n⌊ni⌋g(n) = \sum_{i = 1}^{n} \lfloor \frac ni \rfloor

写出来 n=1e9n = 1e9 的时候 1s1s 内可以过。

求复杂度证明。

2023/7/25 15:23