調和数 mod 素数

$\left(\sum _{i=1}^{n} \frac{1}{i}\right) \bmod{p}$ を計算量 $O(\sqrt{p} \log{p})$ で求める。

計算方法

$ \newcommand{\stirlingfirst}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} $$v := \lfloor\sqrt{n}\rfloor$ とおき、$f_m(x) := \prod_{i=1}^{m}(x+i)$, $g_m(x) := \sum\limits_{i=1}^{m} \dfrac{\prod_{j=1}^{m}(x+j)}{x+i}$ とおくと、$h_m(x) := \sum_{i=1}^{m} \frac{1}{x+i} = \frac{g_m(x)}{f_m(x)}$ が成り立つ。

また、多項式 $f_m(x)$ と $g_m(x)$ は以下の関係式を満たす。$$ \begin{aligned} f_{2m}(x) &= f_m(x) \cdot f_m(x+m)\\ g_{2m}(x) &= g_m(x) \cdot f_m(x+m) + g_m(x+m) \cdot f_m(x) \\ \end{aligned} $$ 後は、前の記事と同様の手法を用いることができる。

よって、$\left(\sum_{i=1}^{n} \frac{1}{i}\right) \bmod{p}$ は $O(\sqrt{p} \log{p})$ で求まる。

補足

  • $\stirlingfirst{n}{k}$ で第 1 種 Stirling 数を表すとき、$H_n := \sum_{i=1}^{n}\frac{1}{n} = \stirlingfirst{n+1}{2} / \stirlingfirst{n+1}{1}$ と書くことができ、上ではこの式を利用している。
  • 同様にして、$\stirlingfirst{n}{i} \bmod{p}$ ($1 \le i \le k$) は $O(k \sqrt{n}\log{n} + k\sqrt{n} \log{k}) = O(k \sqrt{n}\log{(nk)})$ (+ 逆元計算のコスト)で同時に求めることができる。Lagrange 補間に FFT を用いると $O(k \sqrt{n}\log{n})$、$k \sqrt{n}$ 個の評価値の更新の際にも FFT を用いると $O((k\log{k}) \cdot \sqrt{n})$。
  • $\sum\limits_{i=1}^{n} \frac{1}{i^k}$ も同様にして、$O(\sqrt{kn} \log{(kn)})$ で求めることができる。よって、ある素数 $p$ が Wolstenholme 素数であるかどうかは $O(\sqrt{p} \log{p})$ で判定できる($p \ge 11$ に対して、$\sum_{p/6 < i < p/4} \frac{1}{i^3} \equiv 0 \pmod{p}$ $\Leftrightarrow$ $p$ が Wolstenholme 素数)。$\binom{2p-1}{p-1} \equiv 1 \pmod{p^4}$ の判定は、$\pmod{p^4}$ が計算機にとっては厄介。
  • 畳み込みに必要な FFT の回数は $p$ に依存するので、正確には $O(\sqrt{p} \log{p})$ では計算できないはず(今までの $O(\sqrt{p} \log{p})$ 系統は全部そう)。