【莫比乌斯反演】专题总结

先定义一下，数论函数指的定义域是在正整数域下f(1)不等于0的函数。

来自Syu Gau

http://www.zhihu.com/question/23764267/answer/26007647

有以下几个概念

1，卷积：
设 $f,g$ 是两个数论函数（也就是说，以自然数集为定义域的复数值函数），则卷积运算 $fast g$ 定义为
$(fast g)(n) = sum_{ij=n}{f(i)g(j)}$
可以证明，卷积运算满足：
1）交换律： $fast g=gast f$
由定义显然。

2）结合律： $(fast g)ast h=fast(gast h)$
考察两边作用在 $n$ 上，左边是
$egin{align} ((fast g)ast h)(n) &= sum_{lk=n}(fast g)(l)h(k) \ &= sum_{lk=n}left(sum_{ij=l}f(i)g(j) ight)h(k)\ &= sum_{ijk=n} f(i)g(j)h(k) end{align}$
右边是
$egin{align} (fast (gast h))(n) &= sum_{il=n}f(i)(gast h)(l) \ &= sum_{il=n}f(i)left(sum_{jk=l}g(j)h(k) ight)\ &= sum_{ijk=n} f(i)g(j)h(k) end{align}$
故两边相等。

3）存在单位元 $iota$ 使得 $iota ast f=f$
我们需要
$(iotaast f)(n)=sum_{ij=n}iota(i)f(j)=f(n)$
故不难猜到 $iota$ 应该定义为 $iota(n)= egin{cases} 1&n=1\ 0&n eq1 end{cases}$
事实上，直接验证可得
$(iotaast f)(n)=sum_{ij=n}delta_{i,1}f(j)=f(n)$

以上说明数论函数在卷积意义下构成一个交换群。

2，乘法单位元 $u$
上面的 $iota$ 是数论函数在卷积意义下的单位元，而普通乘法 $(fg)(n):=f(n)g(n)$ 意义下的单位元显然是把所有自然数都映到1的函数，记作 $u$ 。

3，莫比乌斯函数 $mu$
$u$ 在卷积意义下的逆元，称为莫比乌斯函数。也就是说 $mu$ 是满足
$uastmu=iota$
的唯一的数论函数。
把这个表达式写开就是
$sum_{dmid n}mu(d)=iota(n)$ …………(*)

通常，莫比乌斯函数 $mu$ 定义为
$mu(1)=1$ ；
$mu(n)=(-1)^k$ ，如果 $n$ 能写成 $k$ 个不同素数之积；
$mu(n)=0$ ，其他情况。

按照这种定义不难证明(*)式。
对于 $n=1$ ，(*)式成立；
对于 $n eq1$ ，用算术基本定理把 $n$ 写成
$n=p_1^{a_1}p_2^{a_2}cdots p_k^{a_k}$
于是
$egin{align} sum_{dmid n}mu(d) =& mu(1)+mu(p_1)+mu(p_2)+cdots+mu(p_k)+mu(p_1p_2)+cdots+mu(p_1p_2cdots p_k) \ =& inom{k}{0}+inom{k}{1}(-1)+inom{k}{2}(-1)^2+cdots+inom{k}{k}(-1)^k \ =&(1-1)^k=0 end{align}$

现在来看看莫比乌斯反演说的是什么呢？
$f(n)=sum_{dmid n}g(d)$
当且仅当
$g(n)=sum_{dmid n}muleft(frac{d}{n} ight)f(d)$
换而言之，
$f = gast u Leftrightarrow g = fastmu$

证明：
$egin{align} f=gast u Rightarrow& fast mu=(gast u)ast mu \ Rightarrow& fastmu=gast(uastmu) \ Rightarrow& fastmu=gastiota \ Rightarrow& fastmu=g end{align}$
反之
$egin{align} g=fastmu Rightarrow& gast u=(fastmu)ast u \ Rightarrow& gast u=fast(muast u) \ Rightarrow& gast u=fastiota \ Rightarrow& gast u=f end{align}$

而关于gcd,我们假设

g(i)代表在i=gcd(x,y)下

f(i)代表在i|gcd(x,y)下

有

f(n)=Σg(d) d|n

g(n)=Σf(d)*u(n/d) d|n

这本质上是一种容斥~

给个模板

ps：莫比乌斯函数与1的卷积是单位卷积。