book
归档: OI 
flag
mode_edit

定理内容

我们知道

$$
F(n)=\sum_{d|n}f(d)
$$

然而。。如果我们要直接求$f(n)$在大多数情况下会很困难,我们考虑用$F(n)$求一下

我们有定理

$$
f(n)=\sum_{d|n}F(d)\mu(\frac{n}{d})
$$

黑人问号.jpg

证明

狄利克雷卷积

为了证明一下上面的定理,我们引入一些骚东西:狄利克雷卷积

狄利克雷卷积定义在数论函数上

运算法则

狄利克雷卷积可以将两个数论函数卷到一起

比如我们有一个$f(x)$,一个$g(x)$

然后把他们卷到一起之后就得到了一个新函数$(f*g)(x)$

那。。这个新函数的表达式是什么呢?

我们定义

$$
(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})
$$

我们观察一下,这个操作是有交换律和结合律的

单位元

同时还存在单位元$\epsilon(n)$使得$\epsilon*f=f$

这个单位元长这样:$\epsilon(n)=[n=1]$

上面的$[n=1]$是一个函数,它的意义是这样的

$$
[n=1]=
\begin{cases}
1&n=1\
0&n\not=1
\end{cases}
$$

现在我们来看一下为什么$\epsilon(n)$是单位元

$$
(\epsilon*f)(n)=\sum_{d|n}\epsilon(d)f(\frac{n}{d})=\
\sum_{d|n}f(\frac{n}{d})[d=1]
$$

我们注意一下这个式子

当且仅当$d=1$时$f(\frac{n}{d})$对答案有贡献,即$\epsilon*f=f$

其它的奇妙的函数

1函数

名字是我瞎口胡的

$1(n)=1$

一个很无聊的函数

比如我们把一个函数$f(n)$卷上一个$1(n)$

$$
(1*f)(n)=\sum_{d|n}f(d)
$$

$\mu$函数

$\mu$是莫比乌斯函数,它的定义是这样的:

$$
\mu=
\begin{cases}
1&n=1\
(-1)^k&n=p_1p_2\cdots p_k\
0&otherwise
\end{cases}
$$

翻译成另一种说法呢?是这样

For any positive integer n, define μ(n) as the sum of the primitive nth roots of unity. It has values in {−1, 0, 1} depending on the factorization of n into prime factors:

  • $\mu (n)=1$ if n is a square-free positive integer with an even number of prime factors.
  • $\mu (n)=-1$ if n is a square-free positive integer with an odd number of prime factors.
  • $\mu (n)=0$ if n has a squared prime factor.

From Wikipedia

它有一个性质:

$$
\sum_{d|n}\mu(d)=[n=1]
$$

我们观察一下,也就是说,$\mu * 1=\epsilon$

证明

终于科普完狄利克雷卷积辣

我们再看一下莫反的两个式子:

$$
F(n)=\sum_{d|n}f(d)
$$

$$
f(n)=\sum_{d|n}F(d)\mu(\frac{n}{d})
$$

我们可以看出

$$
F=1*f
$$

$$
f=\mu*F
$$

我们把下面的式子带进上面

$$
F=1*\mu*F
$$

接下来我们只需要证明$1*\mu=\epsilon$就好啦

这个在前面已经说过辣

所以我们就证明了莫比乌斯反演定理

参考资料


今天就不写游记了qwq

上午的毒瘤比赛题太难受了

大概。。有分就是中位数

qwq

navigate_before navigate_next