メビウス関数(Möbius-Function)
説明
メビウス関数 $\mu(n)$ $(n \in \mathbb{N})$ は, 次のように定義される。
- $\mu(n) = 0$ := $n$ が $1$ 以外の平方数で割り切れる
- $\mu(n) = 1$ := $n$ がもつ相異なる素因数が偶数個
- $\mu(n) = -1$ := $n$ がもつ相異なる素因数が奇数個
メビウスの反転公式(Möbius inversion formula) は以下の関係が成立することを示している。
- $\displaystyle f(n)=\sum _{{d\,\mid \,n}} g(d) \Longleftrightarrow g(n)=\sum _{{d\,\mid \,n}}\mu (\frac n d)f(d)$
ここでは例題として周期的でない長さ $n$ の文字列の数え上げを挙げる。$g(d)$ が周期がちょうど $d$ である文字列の個数(問題の解)で定義すると, $f(n)$ は周期が $n$ の約数である文字列の個数である。ここで $f(n)$ は簡単に求めることができる($=26^n$)ことを利用すると, $g(n)$ を右の式より比較的容易に求めることができる。以下の実装例では $n$ が与えられた時に, この計算に必要な全ての $\mu(\frac n d)$ (つまり $n$ の全ての約数に対してメビウス関数の値を求める) を返すものを実装している。
計算量
$O(\sqrt N)$
実装例