首页 > 其他分享 >『学习笔记』莫比乌斯反演

『学习笔记』莫比乌斯反演

时间:2023-09-04 18:44:42浏览次数:46  
标签:dfrac limits 乌斯 sum mid times mu 反演 莫比

对前置知识的再补充

欧拉函数:

其中一个性质:

\[n = \sum _ {d \mid n} \varphi(d). \]

用狄利克雷卷积表示:

\[\operatorname{id} = \varphi * 1. \]

莫比乌斯函数:

其中一个性质(或叫做定义式):

\[\sum _ {d \mid n} \mu(d) = [n = 1]. \]

用狄利克雷卷积表示:

\[\varepsilon = \mu * 1. \]

其中 \(1\) 函数是常函数,并且 \(1\) 函数的 DGF 就是黎曼 \(\zeta\) 函数。通过上面的补充可知,\(\mu\) 函数和常函数互为逆元。

其他函数

  • \(\sigma_0 = 1 * 1.\)

  • \(\sigma_1 = \sigma_0 * 1.\)

然后就忍不住去推测:

因为 \(\sigma_k(n) = \sum \limits _ {d \mid n} d^k\),(好像不用推测,用 DGF 的方法就能搞出来。)

因为 \(\tilde{S_k}(x) = \tilde{I_k}(x) \times \zeta(x)\),所以 \(\sigma_k = \operatorname{id}_ k * 1\)。

莫比乌斯反演

形式一

\[f(n) = \sum _ {d \mid n} g(d) \iff g(n) = \sum _ {d \mid n} f(d) \times \mu(\dfrac{n}{d}). \]

证明一(卷积):

等价于如下问题:已知 \(f = g * 1\),求证 \(g = f * \mu\)。

因为 \(\varepsilon = \mu * 1\),所以令等式 \(f = g * 1\) 两边同时卷 \(\mu\),可得:

\[f * \mu = g * 1 * \mu = g * \varepsilon = g. \]

得证。

证明二(瞎搞):

等价于如下问题:已知 \(f(n) = \sum \limits _ {d \mid n} g(d)\),求证 \(g(n) = \sum \limits _ {d \mid n} f(d) \times \mu(\dfrac{n}{d})\)。

\[\sum \limits _ {d \mid n} f(d) \times \mu(\dfrac{n}{d}) = \sum \limits _ {d \mid n} f(\dfrac{n}{d}) \times \mu(d) \]

\[= \sum _ {d \mid n} \mu(d) \sum _ {k \mid \frac{n}{d}} g(k) \]

\[= \sum _ {k \mid n} g(k) \sum _ {d \mid \frac{n}{k}} \mu(d) \]

\[= g(n). \]

因为 \(\sum \limits _ {d \mid \frac{n}{k}} \mu(d)\) 当且仅当 \(\dfrac{n}{k} = 1\) 时式子的值为 \(1\),所以显然。

形式二(不常用)

\[f(n) = \sum _ {n \mid d} g(d) \iff g(n) = \sum _ {n \mid d} f(d) \times \mu(\dfrac{d}{n}). \]

懒得证明了,感觉也挺好记的。

标签:dfrac,limits,乌斯,sum,mid,times,mu,反演,莫比
From: https://www.cnblogs.com/Chronologika/p/17676087.html

相关文章

  • ENVI+ERDAS实现Hyperion叶绿素含量反演:经验比值法、一阶微分法
    本文介绍基于ENVI与ERDAS软件,依据Hyperion高光谱遥感影像,采用经验比值法、一阶微分法等,对叶绿素含量等地表参数加以反演的具体操作。目录1前期准备与本文理论部分1.1几句闲谈1.2背景知识1.2.1Hyperion数据介绍1.2.2遥感图像分类方法1.2.3大气校正1.2.4反演算法2基于经验......
  • 反演小记
    反演反演,可以理解为两个事物通过某种关系的互相转化。基本推论设\(F,G\),满足\(F(n)=\sumV[n,i]G(i)\),其中\(V\)为矩阵,将\(F,G\)看成列向量,可以写做\(F=V*G\),那么我们可以容易推出\(G=V^{-1}*F\),这就是反演的过程,而一些特殊的反演即是利用了\(V\)和\(V^{-1}......
  • 【算法学习笔记】max-min容斥 极值反演
    max-min容斥(极值反演)即为下式;\[\begin{equation}\max\{S\}=\sum_{T\subseteqS}(-1)^{|T|+1}\min\{T\}\label{aa}\end{equation}\]\[\begin{equation}\min\{S\}=\sum_{T\subseteqS}(-1)^{|T|+1}\max\{T\}\label{ab}\end{equation}\]证明:证明\(\ref......
  • 「学习笔记」莫比乌斯反演
    「学习笔记」莫比乌斯反演点击查看目录目录「学习笔记」莫比乌斯反演前置知识整除分块积性函数线性筛任意积性函数莫比乌斯反演莫比乌斯函数莫比乌斯反演公式例题[HAOI2011]ProblembYY的GCD[SDOI2014]数表DZYLovesMath[SDOI2015]约数个数和[SDOI2017]数字表格于神之......
  • 『学习笔记』欧拉函数、莫比乌斯函数、高位前缀和、狄利克雷前后缀和
    欧拉函数定义又叫做\(\varphi\)函数,\(\varphi(x)\)用来描述不大于\(x\)且与\(x\)互素的数的个数。性质满足一切积性函数的性质。若\(a\botb\),则\(f(a\timesb)=f(a)\timesf(b)\).能用线性筛或埃氏筛求出。\(\text{from}\1\\text{to}\n\)中与......
  • 学习笔记_莫比乌斯反演
    前置知识:整除分块莫比乌斯函数(\(\mu\))$\mu(d)=\begin{cases}1&(d=1)\\(-1)^{k}&\forallC_i=1\\0&\existsC_i>1\end{cases}$性质1.对于任意正整数\(n\),$$\sum_{d|n}\mu(d)=[n=1]$$[]是一个返回bool型值的判断,当[]内条件成立时返回1,否则返回0.2.对于任意......
  • 单位根反演
    一个非常不阳间的关于单位根的性质:\[\forallk,[n∣k]=\frac{1}{n}\sum_{i=0}^{n−1}\omega^{ik}_{n}\]证明:若\(n∣k\),则有\[Ans=\frac{1}{n}\sum_{i=0}^{n−1}ω^{ink^′}_n=\frac{1}{n}\sum_{i=0}^{n−1}1=1\]否则,等比数列求和有\[Ans=\frac1n\frac{ω^0_n−ω^{nk}_n}......
  • 莫比乌斯反演
    机房卷哥让我写的。大部分是习题总结。不如Wiki两个积性函数\(f,g\),它们的狄利克雷卷积(Dirichlet卷积)为\[h(n)=(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})\]记为\(h=f*g\).狄利克雷卷积满足交换律,结合律,且得到的函数也是积性函数。定义\[\epsilon(n)=\lb......
  • 正泰电力携手图扑:VR 变电站事故追忆反演
    VR(VirtualReality,虚拟现实)技术作为近年来快速发展的一项新技术,具有广泛的应用前景,支持融合人工智能、机器学习、大数据等技术,实现更加智能化、个性化的应用。在电力能源领域,VR技术在高性能计算机和专有设备支持下,已被应用于变电站的培训和安全管理。大力提升了变电站的运行效......
  • 算法学习笔记(24): 狄利克雷卷积和莫比乌斯反演
    狄利克雷卷积和莫比乌斯反演看了《组合数学》,再听了学长讲的……感觉三官被颠覆……目录狄利克雷卷积和莫比乌斯反演狄利克雷卷积特殊的函数函数之间的关系除数函数和幂函数欧拉函数和恒等函数莫比乌斯函数和欧拉函数卷积的逆元莫比乌斯函数与莫比乌斯反演求法数论分块(整除分......