メビウス関数 (Möbius function)
概要
メビウス関数 \(\mu (n)\) は以下のように定義される。
-
\(n\) が素数の二乗で割り切れる時 \(\mu (n) = 0\)
-
それ以外の場合、 \(n\) が \(k\) 個の素因数を持つ時 \(\mu (n) = (-1)^k\)
メビウスの反転公式
以下の関係式を メビウスの反転公式 (Möbius inversion formula) という。
\(\displaystyle f(n) = \sum_{d|n} g(d) \Longleftrightarrow g(n) = \sum_{d|n} \mu \left( \frac{n}{d} \right) f(d)\)
実装
# calculate μ(n): O(√N)
def moebius(n):
x = 2; c = 0
while x*x <= n:
if n % x == 0:
n //= x
if n % x == 0:
return 0
c += 1
x += 1
if n > 1:
c += 1
return -1 if c % 2 else 1
# a table of μ(n) for n in [1, N]
# O(N log log N)
def moebius_table(n):
*p, = range(n+1)
sq = int(n**.5)
for x in range(2, sq+1):
if p[x] == x:
for y in range(x*x, n+1, x):
p[y] = x
for y in range(x*x, n+1, x*x):
p[y] = 0
res = [0]*(n+1)
res[0] = 0; res[1] = 1
for x in range(2, n+1):
res[x] = (p[x] and -res[x//p[x]])
return res
print(moebius(10))
# => "1"
print(moebius_table(20))
# => "[0, 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, 0]"参考
-
秋葉拓哉, 岩田陽一, and 北川宜稔. "プログラミングコンテストチャレンジブック." (2010).