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

莫比乌斯反演 学习笔记

时间:2023-10-10 18:56:53浏览次数:36  
标签:frac 函数 乌斯 sum mid mu 反演 莫比 displaystyle

前置知识

整除分块

把之前写的博客搬过来了

模型

求 \(\large\sum^{n}_ {i=1} \lfloor{\frac{n}{i}}\rfloor\)

假设 \(n\) 等于 10,我们可以列出下表:

\(\ i\) 1 2 3 4 5 6 7 8 9 10
\(\frac{10}{i}\) 10 5 3 2 2 1 1 1 1 1

如果我们的 \(n\) 更大时,我们可以发现 \(\frac{10}{i}\) 中有许多重复的地方。

我们可以将相同的分为一块,这样可以发现块不会超过 \(2\sqrt n\) 个。

证明
我们设当前块的值为 \(m\):
当 \(m\le \sqrt n\) 时,\(\frac nm\) 总共的个数,不会超过 \(m\) 的个数,因此最多有 \(\sqrt n\) 个块。
当 \(m> \sqrt n\) 时,\(\frac nm\) 的取值应该在 \([1,\sqrt n]\) 之间,因此也最多有 \(\sqrt n\) 个块。

综上,块的个数不超过 \(2\sqrt n\)。

推导

我们需要找到每个块的左右端点,设我们已知这个块的左端点 \(l\),则考虑怎么找到右端点 \(r\)。

设这个块的值为 \(x\),那么对于块中的每个数 \(i\),则有 \(x=\lfloor{\frac{n}{l}}\rfloor=\lfloor{\frac{n}{i}}\rfloor\)。

那么 \(r=max(i)\),因为 \(i\times x\le n\),我们可以设 \(i\times x=n\) 以此来找到最大的 \(r\)。

则 \(\large r=\lfloor{\frac{n}{x}}\rfloor=\bigl\lfloor{\frac{n}{\lfloor{n/l}\rfloor}}\bigl\rfloor\)。

下一个块的 \(l'\) 就应该是 \(r+1\)。

积性函数

定义:积性函数指对于所有互质的整数 \(a\) 和 \(b\) 有性质 \(f(ab)=f(a)f(b)\) 的数论函数,且积性函数与积性函数的卷积还是积性函数。

一些常见的积性函数如:
\(1(n)=1\) 常数函数

\(ID(n)=n\) 单位函数

\(\epsilon(n)=[n==1]\) 单位元函数

\(d(n)=\displaystyle\sum_{d\mid n}1\),因子函数,\(n\) 的正因子的个数。

\(\sigma(n)=\displaystyle\sum_\limits{d\mid n}d\),因子和函数,\(n\) 的各个约数之和。

\(\varphi(n)=\displaystyle\sum^n_{i=1}[gcd(n,i)=1]\) 欧拉函数,表示比不大于 \(n\) 且与 \(n\) 互质的数的个数。

\(\mu(n)\) 莫比乌斯函数(等下会讲)

一些需要记得
\((\mu* 1)=\epsilon\)

\((\varphi* 1)=ID\)

\((\mu* ID)=\varphi\)

狄利克雷卷积

我们需要定义两个积性函数的一个运算符号:$* $ 狄利克雷卷积。

这名字听起来有点高深,不过你可以将它想象成一个定义新运算。

定义

两个数论函数 \(f\) 和 \(g\) 的狄利克雷卷积为:$$(f* g)=\displaystyle\sum_{d\mid n} f(d)\times g(\frac{n}{d})=\displaystyle\sum_{d\mid n} f(d)\times g(\frac{n}{d})$$

性质

  • 交换律 \(f* g=g* f\)
  • 结合律 \(f* (g* h)=(f* g)* h\)
  • 分配律 \(f* h+g* h=(f+g)* h\)
  • 单位元 \(\epsilon * f=f\)
  • \((xf)* g=x(f* g)\)

前三个和乘法的运算法则一样,可以简单来记。至于证明,我们对于 \(f* g\),也就是遍历每两个 \(n\) 的对应约数在两个积性函数中的值之积,当我们跟换左右两边或者顺序的时候,每个约数的贡献不会发生改变。

莫比乌斯函数

莫比乌斯函数 \(\mu(x)\) 的定义是:

\[\mu(x)=\begin{cases}1&(x=1)\\0&(p^2\mid x)\\(-1)^{\omega(x)}&(\omega(x)\texttt{表示 x 的质因子个数})\end{cases} \]

也就是说,当 \(d=1\) 时,\(\mu(d)=1\);

当 \(d\) 有平方因子的时候,\(\mu(d)=1\);

当 \(d=\displaystyle\prod_{i=1}^k p_i\),\(p_i\) 为质数且互不相等时,则有 \(\mu(d)=(-1)^k\)。

莫比乌斯函数也有很多有趣的性质

  • \(\displaystyle\sum_{d\mid n}\mu(d)=[n==1]\Rrightarrow \mu*I=\epsilon\)。

  • \(\dfrac{\varphi(n)}{n}=\displaystyle\sum_{d\mid n}\frac{\mu(d)}{d}\)(等会会证明)

然后就是线性筛筛 \(\mu\):

void Get_mu(int x){
   	isprime[1]=1;
   	mu[1]=1;
   	for(int i=2;i<=x;i++){
		if(!isprime[i])
			prime[++tot]=i,mu[i]=-1;
		for(int j=1;j<=tot&&i*prime[j]<=x;j++){
			isprime[prime[j]*i]=1;
			if(i%prime[j]==0) break;//处理平方因子的情况,因为 i 里面有prime[j] 了,
//所以 $i*prime[j]$ 有平方因子,又由于 线性筛每个数只筛一个,那么不会有重复的情况,导致值不一样。
			mu[i*prime[j]]=-mu[i];
		}
	}
}

欧拉函数

欧拉函数的定义是:比不大于 \(n\) 且与 \(n\) 互质的数的个数,也就等于

\[\varphi(n)=\displaystyle\sum^n_{i=1}[gcd(n,i)=1] \]

然后我们也可以把它表示为狄利克雷卷积的形式:

\[\varphi*1=ID \]

然后我们将它左右两边同时卷上一个 \(\varphi\)。

由于我们知道:

\[\because(\mu*1)=\epsilon \]

\[\therefore\varphi*1*\mu=ID*mu \]

\[\therefore \varphi*\epsilon=ID*\mu \]

\[\therefore \varphi=ID*\mu \]

\[\therefore \varphi(n)=\displaystyle\sum_{d\mid n}\mu(d)\times \frac{n}{d} \]

两边同时除以 \(n\) 我们就能得到:$$\dfrac{\varphi(n)}{n}=\displaystyle\sum_{d\mid n}\frac{\mu(d)}{d}$$(上面莫比乌斯函数的性质二就得到证明了)。

莫比乌斯反演

定理:若 \(F(n)\) 与 \(f(n)\) 是两个定义在非负整数集合上的两个积性函数,且满足条件:

\[F(n)=\displaystyle\sum_{d\mid n}f(d) \]

那么有结论:

\[f(n)=\sum_{d\mid n}\mu(d)F(\lfloor{\frac{n}{d}}\rfloor) \]

证明

因为我们知道

\[F(n)=\displaystyle\sum_{d\mid n}f(d) \]

那么可以将这个式子表示为:

\[F=f*I \]

想欧拉函数中的式子一样再将左右两边同时卷上 \(\mu\),可得:

\[\because F*\mu=f*1*\mu \]

\[\therefore F*\mu=f*\epsilon=f \]

\[\therefore f(n)=\displaystyle\sum_{d\mid n}\mu(d)F(\lfloor{\frac{n}{d}}\rfloor) \]

\[\Rightarrow f(n)=\displaystyle\sum_{n\mid d}\mu(\frac{d}{n})F(d) \]

标签:frac,函数,乌斯,sum,mid,mu,反演,莫比,displaystyle
From: https://www.cnblogs.com/pdpdzaa/p/17754451.html

相关文章

  • 莫比乌斯函数
    推荐视频:518筛法求莫比乌斯函数前提知识:莫比乌斯函数点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defineLLlonglongconstintN=1e8+10;intp[N],cnt;intmu[N];//d[i]记录i的约数的和boolvis[N];voidget_mu(intn){//筛法求约数的个数 mu[......
  • 莫比乌斯反演小记
    基本内容莫比乌斯函数\(\mu\)定义为\(1\)的逆。一些小性质:\(\mu*1=\epsilon\)\(\mu*\text{id}=\varphi\)反演内容我的理解是:\[[a=1]=\sum\limits_{d|a}\mu(d)\]典型例题例1P2398GCDSUM求\[\sum\limits_{i=1}^n\sum\limits_{j=1}^n\gcd(i,j)\]来推下式......
  • 莫比乌斯反演乱写
    太久没有写莫反的题,忘完了。。。简单写写当总结常见数论函数\(e(x)=[x=1]\)\(I(x)=1\)\(id(x)=x\)以上函数完全积性\(\varphi(x)=\sum\limits_{i=1}^{x-1}[\gcd(i,x)==1]\)\(\mu=I^{-1}\)\(d(x)=\sum\limits_{i=1}^{x}[i\midx]\)以上是......
  • 「学习笔记」莫比乌斯反演
    开新坑了。QWQ前置芝士:数论分块。(之后再说。QWQ)积性函数定义一个数论函数\(f(n)\)满足\(f(xy)=f(x)\timesf(y)\)(\(\gcd(x,y)=1\)),则称\(f(n)\)是积性函数。莫比乌斯函数:\(\mu(n)=\begin{cases}1&n=1\\0&n\\text{含有平方因子}\\(-1)^k&k\text{为}\n\\text{的......
  • 可持久化非确定状态AC自动分块维护线段平衡仙人掌优化最小费用最大流预处理混合图上莫
    P8946TheLostSymbol这种类型的dp的特点就是大部分转移形如\(f(i,j)\rightarrowf(i+1,j+1)\)之类的,并且当以上转移出现时原数组被清空,这就可以用一个deque来维护,然后对于全局赋值/全局加,需要对每个位置维护一个时间戳,并记录上一次赋值/加是什么时候,以便标记下传。(貌似......
  • 『学习笔记』莫比乌斯反演
    对前置知识的再补充欧拉函数:其中一个性质:\[n=\sum_{d\midn}\varphi(d).\]用狄利克雷卷积表示:\[\operatorname{id}=\varphi*1.\]莫比乌斯函数:其中一个性质(或叫做定义式):\[\sum_{d\midn}\mu(d)=[n=1].\]用狄利克雷卷积表示:\[\varepsilon=\mu*1.\]......
  • 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]数字表格于神之......