有没有快速求 H(n) 的方法

ppip @ 2022-12-03 21:41:57

by ppip @ 2022-12-03 21:42:16

在剩余系下。

by Register_int @ 2022-12-03 21:46:07

@ppip P5702 调和级数求和
（感觉没必要）

by Register_int @ 2022-12-03 21:46:44

而且有没有可能可以线性递推逆元。

by lsj2009 @ 2022-12-03 21:48:41

@ppip 是指求 \sum\limits_{i=1}^n \frac{1}{i}\bmod{p} 吗？如果是的，直接 O(n\log n) 算和 O(n) 应该没有太大区别；如果真要 O(n) 其实相当于求 1\sim n 的逆元之和，直接用递推公式或者 O(n+\log n) 处理出阶乘逆元，再作商即可。

by ppip @ 2022-12-03 21:49:59

@lsj2009 @Register_int 感谢，此帖结。

by lsj2009 @ 2022-12-03 21:50:07

等一下……o(n) 指 O(n) 吗？如果不是，当我什么都没说。

by Register_int @ 2022-12-03 21:52:50

@lsj2009 小于。

by jijidawang @ 2022-12-04 07:49:14