zcmimi's blog
avatar
zcmimi
2020-03-14 22:46:00

数论函数

  1. 加法

    逐项相加

    (f+g)(x)=f(x)+g(x)

  2. 数乘

    (xf)(n)=x\cdot f(n)

定义

两个数论函数的狄利克雷卷积∗

t=f*g等价于

t(n)=\sum_{i|n}f(i) \cdot g(\frac ni)

等价于

t(n)=\sum_{ij|n}f(i) \cdot g(j)

性质

  1. 交换律f*g=g*f

  2. 结合律f*(g*h)=(f*g)*h

  3. 分配率f*h+g*h=(f+g)*h

  4. (xf)*g=x(f*g)

  5. 单位元\epsilon*f=f

以上5个结论都可以通过带入得到

  1. 逆元

    对于每个f(1) \not = 0的函数f,都存在f*g=\epsilon

    定义

    g(n)=\frac{1}{f(1)}\left([n=1]-\sum_{i|n,i\neq 1}f(i)g(\frac{n}{i})\right)

    那么

    \sum_{i|n}f(i)g(\frac{n}{i})\\=f(1)g(n)+\sum_{i|n,i\neq1}f(i)g(\frac{n}{i})\\=[n=1]-\sum_{i|n,i\neq 1}f(i)g(\frac{n}{i})+\sum_{i|n,i\neq 1}f(i)g(\frac{n}{i})\\=[n=1]

常用的函数与与常用卷积关系

几个常用的函数:

  • \epsilon(n)=[n=1]
  • 1(n)=1
  • Id(n)=n
  • 莫比乌斯函数: \mu(i)=\begin{cases}1,i=1\\(-1)^k,i=p_1\times p_2\times \dots \times p_k\\0,rest\end{cases}
  • 欧拉函数: \varphi(n)=n\prod_{i=1}^k(1-\frac 1{p_i})(n={p_1}^x\times {p_2}^x\times \dots \times {p_k}^x)
  • 约数数: d(n)=\sum_{d|n}1(d=1*1)
  • 约数和: \sigma(n)=\sum_{d|n}d(\sigma=1*Id)

    \sigma_0(n)表示n的因数个数

    \sigma_k(n)表示所有因数的k次方和

  • \lambda(n)=(-1)^k

常用卷积关系

  1. \mu * 1=\epsilon(莫比乌斯反演,\mu1互为逆元)

    如果f * 1=g,那么f=f * \epsilon=f * 1 * \mu=\mu * g

    证明(摘自 https://www.luogu.com.cn/blog/lx-2003/mobius-inversion ):

    对此只需要定义:

    (\mathbf f\oplus\mathbf g)(x)=\sum_{x\mid y}\mathbf f(y/x)\mathbf g(y)

    并容易证明:

    (\mathbf f\ast\mathbf g)\oplus\mathbf h=\mathbf f\oplus(\mathbf g\oplus\mathbf h)

    于是

    \mathbf f=(\mu\ast\mathbf1)\oplus\mathbf f=\mu\oplus(\mathbf1\oplus\mathbf f)=\mu\oplus\mathbf g

  2. \varphi * 1 = Id

    根据1.

    \varphi=\mu*Id

    证明(摘自 https://www.luogu.com.cn/blog/lx-2003/mobius-inversion ):

    n=\prod_{i=1}^t p_i^{k_i}

    \sigma_0\varphi在素数幂处的值很容易得到: k>0\sigma_0(p^k)=k+1,\varphi(p^k)=p^{k-1}(p-1)

    所以:

    \sigma_0(n)=\prod_{i=1}^t(k_i+1), \varphi(n)=\prod_{i=1}^np_i^{k_i-1}(p_i-1)=n\prod_{i=1}^t\left(1-\frac1{p_i}\right)

    (\varphi\ast\mathbf1)(p^k)\\=\sum_{i|p^k}\varphi(i)1(\frac{p^k}i)\\=1+\sum_{i=1}^k p^{i-1}(p-1)\\=1+(p-1)+p^2-p+p^3-p^2+...+p^k-p^{k-1}\\=p^k

    带入求解可以得出Id=\varphi*1

  3. d=1*1
  4. 1=\mu * d

卷积证明莫比乌斯反演: F=f*1,f=\mu * F

强烈推荐: https://www.luogu.com.cn/blog/lx-2003/mobius-inversion

狄利克雷卷积
comment评论
Search
search