ei1333's page

メビウス関数(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)$

実装例

map< int64_t, int > moebius(int64_t n) {
  vector< int64_t > factor;
  for(int64_t i = 2; i * i <= n; i++) {
    if(n % i == 0) {
      factor.emplace_back(i);
      while(n % i == 0) n /= i;
    }
  }
  if(n > 1) factor.emplace_back(n);

  map< int64_t, int > ret;
  for(int i = 0; i < (1 << factor.size()); i++) {
    int mu = 1;
    int64_t dd = 1;
    for(int j = 0; j < factor.size(); j++) {
      if((i >> j) & 1) {
        mu *= -1;
        dd *= factor[j];
      }
    }
    ret[dd] = mu;
  }
  return ret;
}