G - Divisible by 3 解説 by kyopro_friends

Powerful Number Sieveについて

公式解説の発展的な話題として触れられている powerful number 篩についての解説をします。

なお、本問題を powerful number 篩を用いて高速化することはできません。（多分）

節1　Powerful number について

定義1-1

  • 正整数 \(N\) が powerful number ⇔「任意の素数 \(p\) について、\(p|N \Rightarrow p^2|N\)」
  • 正整数 \(N\) が square free number ⇔「任意の整数 \(n\) について、\(n^2\not|N\)」

補題1-1

\(N\) 以下の square free number の列挙は \(O(N)\) で可能。

証明：
長さ \(N\) の真偽値の配列を持ち、4の倍数、9の倍数、16の倍数……を順に記録していけばよい。
\(\frac{N}{4}+\frac{N}{9}+\frac{N}{16}+\ldots\leq N\int_{x\geq 1}x^{-2}dx=N\)

補題1-2

\(2\) 以上の整数は、非負整数 \(n\) と \(m\in\{0,1\}\) を用いて、\(2n+3m\) の形に一意に表すことができる。

補題1-3

powerful number は、正整数 \(a\) と square free number \(b\) を用いて \(a^2 b^3\) の形に一意に表すことができる。

証明：
素数ごとに指数を考えることで補題1-2より明らか。

定理1-1

\(N\) 以下の powerful number の個数は \(O(\sqrt{N})\) である。

証明：
補題1-3より、\(N\) 以下のpowerful numberの個数は \(\sum_{b\geq 1}\left\lfloor\sqrt{\frac{N}{b^3}}\right\rfloor\leq \sqrt{N}(1+\int_{x\geq 1} x^{-1.5}dx)=2\sqrt{N}\)

定理1-2

\(N\) 以下の powerful number の列挙は \(O(\sqrt{N})\) で可能。

証明： 補題1-1, 補題1-3, 定理1-1 を組み合わせると明らか。

節2　乗法的関数とディリクレ畳み込みについて

定義2-1

  • 正整数に対して定義された関数 \(f\) が乗法的 (multiplicative) である ⇔ 「正整数 \(a,b\) が互いに素である ⇒ \(f(ab)=f(a)f(b)\)」

補題2-1

乗法的関数 \(f\) は、素数 \(p\) と非負整数 \(e\) の対全てに対して \(f(p^e)\) が定まると一意に定まる。

定義2-2

  • 乗法的関数 \(f,g\) に対してそのディリクレ畳み込み \(f*g\) を \((f*g)(n)=\sum_{ij=n}f(i)g(j)\) と定める。
  • ゼータ関数 \(\zeta\) を、任意の正整数 \(n\) に対して \(\zeta(n)=1\) を満たす関数と定める。
  • メビウス関数 \(\mu\) を、\(\mu(1)=1\)、\(n \geq 2 \Rightarrow (\mu*\zeta)(n)=0\) を満たす(唯一の)関数と定める。

補題2-2

ディリクレ畳み込みは可換であり、結合的である。

節3　乗法的関数の prefix sum について

事実3-1

\(f\) が乗法的であるとき、\(\sum_{n=1}^{N}f(n)\) を \(O(N^{3/4})\) で求めることができる。

定理3-1

\(\sum_{n=1}^{N}(\zeta*f)(n)=\sum_{n=1}^{N}\left\lfloor\frac{N}{n}\right\rfloor f(n)\)

証明： 両辺で \(f(n)\) の寄与回数を考えると明らか

系3-1

\(\sum_{n=1}^{N}f(n)=\sum_{n=1}^{N}\left\lfloor\frac{N}{n}\right\rfloor (\mu*f)(n)\)

例3-1

乗法的関数 \(f\) は \(f(p^e)=p^{e-1}\) を満たすとする。このとき、\(\sum_{n=1}^{N}f(n)\) を \(\tilde{O}(\sqrt{N})\) で求める方法を述べる。

系3-1から求める値は \(\sum_{n=1}^{N}\left\lfloor\frac{N}{n}\right\rfloor (\mu*f)(n)\) である。 ここで

\((\mu*f)(p^e)=\begin{cases} 0 && \text{if } e=1 \\ p^{e-1}-p^{e-2} && \text{if } e\geq 2 \end{cases}\)

であることに注意すると結局、\((\mu*f)(n)\neq 0\) となるのは n が powerful number であるときに限る。 よって powerful numberを列挙して愚直に和をとることで、\(f(n)\) を高速に求めるための適当な前計算を含め \(\tilde{O}(\sqrt{N})\) により計算可能。

この例のように、powerful number 以外の箇所では値が消えるような関数をうまく用意できれば、\(\sum_{n=1}^{N}f(n)\) を高速に求めることができる。これが powerful number 篩の本質的なアイディアである。

この変形をシステマティックに述べると次のようになる。

定理3-2

乗法的関数 \(f,g,h\) が \(f=g*h\) を満たすとき

\(\sum_{n=1}^{N}f(n) = \sum_{ij\leq N}g(i)h(j) = \sum_{j=1}^{N}(\sum_{i\leq N/j}g(i))h(j)\)

が成り立つ。また、3条件

  • 任意の素数 \(p\) で \(h(p)=0\)
  • 各 \(j\) に対する \(\sum_{i=1}^{N/j}g(i)\) の列挙が全体で \(O(\sqrt{N})\)
  • 各 powerful number \(j\) に対する \(h(j)\) の列挙が全体で \(O(\sqrt{N})\)

を満たすとき、この値は \(O(\sqrt{N})\) で計算可能。

例3-1は \(g=\zeta\)、\(h=\mu*f\) という例だった。 実際には2つ目の条件が厳しく、実用的なものは \(g(n)=n^k\) のようなものに限られる（？）。
しかしここで \(\tilde{O}(N^{2/3})\) 時間かけて全体の計算量が悪化することを許容すると、ディリクレ畳み込みの形で表せるもの、例えば約数関数 \(g(p^e)=\sum_{i=0}^{e}p^{ki}\) やトーティエント関数 \(g(p^e)=p^{e-1}(p-1)\) なども利用できることになり、活用の幅が広がる。

参考文献

投稿日時:
最終更新: