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

【学习笔记】莫比乌斯反演

时间：2023-10-23 17:25:50浏览次数：36  
标签：frac 函数 积性 乌斯 sum mid mu 反演 莫比

前言/声明

首先，本人的数论水平极低，目前莫反只是刚刚入门的水平，此博客的主要作用是用于记录本人的学习过程，真的想要深入了解莫反的话这边推荐 cmd 大佬的博客（点这里），应该对你有更大帮助。

建议学习的时候能多理解些就多去理解，少硬记些结论，这样更不容易忘记。

前置知识：最基础的数论。

0 基本定义与符号

  • 整除：对于任意两个整数 \(a,b\)，如果有 \(a\bmod b=0\)，则称 \(b\) 整除 \(a\)，记作 \(b\mid a\)。
  • 最大公约数：对于任意两个整数 \(a,b\)，称 \(d\) 是 \(a,b\) 的最大公约数当且仅当 \(d\) 是能整除 \(a,b\) 的最大整数，记作 \(\gcd(a,b)\)，或简记为 \((a,b)\)。
  • 艾弗森括号：\([???]\) 表示的是，如果中括号内的东西为真，则值为 \(1\)，否则为 \(0\)。比如：\([1.14>0.514]=1,\ [2<9]=0\)。
  • 欧拉函数：对于正整数 \(n\)，欧拉函数表示 \([1,n]\) 内与 \(n\) 互质的正整数的个数，记作 \(\varphi(n)\)。

1 数论函数与狄利克雷卷积

1.1 数论函数

定义：定义域为正整数（陪域为复数）的函数。

如果下文中没有特殊说明，所有提到的函数都是数论函数，所有提到的数也均为整数。

1.1.1 积性函数

定义：如果数论函数 \(f\) 满足对于任意两个互质的正整数 \(a,b\) 都有 \(f(a)f(b)=f(ab)\)，则称 \(f\) 是一个积性函数。

就比如大家应该很熟悉的欧拉函数 \(\varphi\)，以及下文会提到的莫比乌斯函数 \(\mu\)，都属于积性函数。

1.1.2 完全积性函数

定义：如果数论函数 \(f\) 满足对于任意两个正整数 \(a,b\)，没有任何其他限制，都有 \(f(a)f(b)=f(ab)\)，则称 \(f\) 是一个完全积性函数。

下面，为大家介绍几个下文会经常用到的完全积性函数：

  • 恒等函数 \(I\)，对于所有正整数 \(n\)，都有 \(I(n)=1\)，经常作为废话出现。
  • 元函数 \(e\)，对于所有正整数 \(n\)，\(e(n)=[n=1]\)，即当且仅当 \(n=1\) 时值为 \(1\)，否则为 \(0\)，是狄利克雷卷积的单位元（下文会提到）。
  • 单位函数 \(id\)，对于所有正整数 \(n\)，\(id(n)=n\)。
  • 幂函数 \(id^x\)，对于所有正整数 \(n\)，\(id^x(n)=n^x\)，单位函数是幂函数的特殊情况。

显然，完全积性函数 \(\in\) 积性函数。

1.2 狄利克雷卷积

定义：设 \(f\) 和 \(g\) 是两个数论函数，则它们的狄利克雷卷积是一个新的数论函数，记作 \(f*g\)，规则如下：

\[f*g(n)=\sum_{d\mid n}f(d)g(\frac{n}{d}) \]

可以理解为对数论函数定义的一种运算。

比如，\(f*g(8)=f(1)g(8)+f(2)g(4)+f(4)g(2)+f(8)g(1)\)。

狄利克雷卷积满足以下运算律：

  • 交换律：\(f*g=g*h\)。
  • 结合律：\(f*g*h=f*(g*h)\)。
  • 分配律：\(f*(g+h)=f*g+f*h\)，这里数论函数的加法定义为点值相加，即 \((f+g)(n)=f(n)+g(n)\)。

比较显然，直接把式子套上去就能证明，具体过程这里不再给出。

对于任意数论函数 \(f\)，总是有 \(f*e=f\)，因此 \(e\) 是狄利克雷卷积的单位元。

证明：\(f*e(n)=\sum_{d\mid n}f(d)e(\frac{n}{d})\)，显然当且仅当 \(\frac{n}{d}=1\)，即 \(d=n\) 时 \(f(d)\) 对结果才会有贡献。

对于任意数论函数 \(f\) 和 \(g\)，如果 \(f*g=e\)，则称 \(g\) 是 \(f\) 在狄利克雷卷积意义下的逆，也记作 \(f^{-1}\)。

1.3 相关性质

  • 对于一个积性函数 \(f\)，一定有 \(f(1)=1\)。

    证明：由积性函数定义，得 \(f(1)=f(1)f(1)\)，所以 \(f(1)=1\)。

  • 对于一个积性函数 \(f\)，\(f(n)=f(p_1^{e_1})f(p_2^{e_2})...f(p_m^{e_m})\)，其中 \(p_1,p_2,...p_m\) 和 \(e_1,e_2,...,e_m\) 分别对应 \(n\) 质因数分解后的每个质因子及其对应次数。

    证明：\(p_1^{e_1},p_2^{e_2},...,p_m^{e_m}\) 显然互质，由积性函数定义可得上式。

  • 两个积性函数的狄利克雷卷积仍是积性函数。

    证明：设 \(f,g\) 是两个积性函数，\(a,b\) 是两个互质的正整数，它们的狄利克雷卷积为 \(h\)。

    \[\begin{aligned} h(a)h(b)&=\sum_{d\mid a} f(d)g(\frac{a}{d}) \sum_{t\mid b} f(t)g(\frac{b}{t}) \\ &=\sum_{d\mid a} \sum_{t\mid b} f(d)f(t)g(\frac{a}{d})g(\frac{b}{t}) \end{aligned} \]

    考虑合并求和符号，改为枚举 \(dt\)，\(\sum\) 右边的部分显然可以根据积性函数性质合并：

    \[\begin{aligned} &=\sum_{dt\mid ab} f(dt)g(\frac{ab}{dt}) \\ &=h(ab) \end{aligned} \]

    原命题得证。

2 莫比乌斯函数

了解了上面的前置知识之后，我们就可以逐步引出主角莫比乌斯函数了。

2.1 来源

假设现在有两个单变量函数 \(F\) 和 \(f\)，它们之间满足如下关系：

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

如果 \(f\) 函数的值易求，那么我们显然根据上式就可以算出 \(F\) 的值了。

不过现在又有一个新的问题，如果易求的函数是 \(F\)，那么我们该如何求出 \(f\) 的值呢？

我们考虑将上面的式子变为狄利克雷卷积的形式：

\[\begin{aligned} F(n)&=\sum_{d\mid n} I(d)*f(d) \\ F&=I*f \end{aligned} \]

两边同时乘上 \(I\) 的逆，即 \(I^{-1}\)，可得：

\[f=F*I^{-1} \]

那么如果我们能够求出 \(I^{-1}\) 是什么，\(f\) 也就能够求出来了。

而这个 \(I^{-1}\)，就是我们的莫比乌斯函数 \(\mu\)。

但是新的问题又来了，\(\mu\) 函数的值到底是什么呢？

2.2 定义

首先，\(\mu\) 是一个积性函数，因为积性函数的逆还是积性函数。

而一个积性函数的逆其实是可以构造出来的，具体构造的方法：点这里查看。

因为比较复杂（其实是我不会），具体过程这里不再具体给出。

莫比乌斯函数的定义如下：

  • 若 \(n=1\)，则 \(\mu(n)=1\)。
  • 若 \(n=p_1p_2...p_k\)，\(p_i\) 是互不相同的质数，那么 \(\mu(n)=(-1)^k\)。
  • 否则 \(\mu(n)=0\)。

显然，\(\mu\) 的取值只有 \(-1,0,1\) 三种，这决定了其本质其实为容斥系数。

2.3 相关性质

  • 对于任意的正整数 \(n\)，总是有：

    \[e(n)=\sum_{d\mid n}\mu(d) \]

    显然，因为 \(\mu=I^{-1}\)，而上式等价于 \(e=\mu*I\)。下面给出具体证明过程：

    • 当 \(n=1\) 时显然成立。

    • 当 \(n\not=1\) 时，对 \(n\) 进行质因子分解得 \(n=p_1^{e_1}p_2^{e_2}...p_k^{e_k}\)。在 \(n\) 的所有因子当中，当且仅当其所有质因子次数都是 \(1\) 时 \(\mu\) 值才不为 \(0\)，而含有 \(r\) 个不同质因子的因子有 \(C_k^r\) 个，那么显然有：

      \[\begin{aligned} \sum_{d\mid n}\mu(d)&=C_k^0-C_k^1+C_k^2+...+(-1)^kC_k^k \\ &=\sum_{i=0}^k(-1)^iC_k^i \end{aligned} \]

      根据二项式定理 \(\sum_{i=0}^kC_k^ix^iy^{n-i}=(x+y)^k\)，令 \(x=-1,y=1\)，代入可得原式为 \(0\)。

  • 对于任意的正整数 \(n\)，总是有：

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

    上式等价于 \(\varphi=\mu*id\)，证明涉及较复杂的容斥，不具体展开。

2.4 程序求解

  • 质因数分解暴力求解，直接根据定义即可，单次复杂度 \(\mathcal{O}(\sqrt n)\)。

  • 根据积性函数性质，线性筛预处理，总复杂度 \(\mathcal{O}(n)\)。

    void init(int n){
		memset(isPrime,1,sizeof(isPrime));
		isPrime[1]=0;mu[1]=1;
		For(i,2,n){
			if(isPrime[i]) pri[++cnt]=i,mu[i]=-1;
			For(j,1,cnt){
				if(i*pri[j]>n) break;
				isPrime[i*pri[j]]=0;
				mu[i*pri[j]]=(i%pri[j]==0)?0:-mu[i];
				if(i%pri[j]==0) break;
			}
		}
}

3 莫比乌斯反演公式

  • 公式一：

    \[[n=m]=[n|m]\sum_{d\mid (n/m)}\mu(d) \]

    证明：显然 \([n=m]\Leftrightarrow[n\mid m][n/m=1]\)，由 \(e=\mu*I\)，用 \(e(n/m)\) 替换掉 \([n/m=1]\) 可得上式。

  • 公式二：

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

    证明：见上文 2.1 部分，不再重复。

  • 公式三：

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

    限于本人水平，不证。

4 例题

目前准备了三四道，但都是十分基础的那种入门题，有空立马来写。。。

4.1 公式一的应用

公式一是最好掌握，但也是最需要掌握的内容，下面我们来几道题实战一下。

【例题一】互质数对

题目大意：\(Q\) 次询问，每次给定 \(n,m\)，求

\[\sum\limits_{i=1}^n\sum\limits_{j=1}^m[(i,j)=1] \]

其中 \(1\le n,m,Q\le 10^5\)，\(m\le n\)。

题目分析：考虑用公式一来替换 \([(i,j)=1]\)，变成求解：

\[\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid (i,j)}\mu(d) \]

考虑一个经典结论：\(d\mid(i,j)\Leftrightarrow d\mid i\land d\mid j\)，此时变为求解：

\[\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid i\land d\mid j}\mu(d) \]

再接下来，我们再使用一个经典套路——交换枚举顺序，观察交换后的新限制。

考虑如果我们先枚举 \(d\)，那么此时就变为了给 \(i\) 和 \(j\) 分别添加了 \(d\mid i\) 和 \(d\mid j\) 的限制，变成了：

\[\sum_{d=1}^n\mu(d)\sum_{d\mid i}\sum_{d\mid j}1 \]

考虑 \(\sum\limits_{d\mid i}\sum\limits_{d\mid j}1\) 这项如何处理，其实就相当于是 \(n\) 以内 \(d\) 的倍数的数量和 \(m\) 以内 \(d\) 的倍数的数量之积，显然前者其实就是 \(\lfloor\frac{n}{d}\rfloor\)，后者其实就是 \(\lfloor\frac{m}{d}\rfloor\)，那么现在就变成了：

\[\sum_{d=1}^n\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor \]

如果我们用线性筛预处理 \(\mu\)，现在单次询问的复杂度已经降到了 \(\mathcal{O}(n)\)，但对于题目中的数据范围还是无法通过。

但是很显然 \(\sum\) 后面的那些可以使用预处理 \(\mu\) 前缀和+整除分块的方法，这样我们单次询问的复杂度可以做到 \(\mathcal{O}(\sqrt n)\)，总时间复杂度降为 \(\mathcal{O}(n+T\sqrt{n})\)，问题解决。

如果你不会整除分块，点这里。

int T,n,m,cnt,pri[N],mu[N],sm[N];
bool isPrime[N];

void init(int n){  //预处理 mu
	memset(isPrime,1,sizeof(isPrime));
	isPrime[1]=0;mu[1]=-1;
	For(i,2,n){
		if(isPrime[i]) pri[++cnt]=i,mu[i]=1;
		For(j,1,cnt){
			if(i*pri[j]>n) break;
			isPrime[i*pri[j]]=0;
			mu[i*pri[j]]=(i%pri[j]==0)?0:-mu[i];
			if(i%pri[j]==0) break;
		}
	}
	For(i,1,n) sm[i]=sm[i-1]+mu[i];  //对 mu 前缀和
}

ll calc(int n,int m){  //整除分块
	ll ans=0;
	for(int l=1,r=0;l<=min(n,m);l=r+1){
		r=min(n/(n/l),m/(m/l));
		ans+=1ll*(n/l)*(m/l)*(sm[r]-sm[l-1]);  //计算答案
	}
	return ans;
}

void Main(){
	init(1e5);read(T);
	while(T--){
		read(n,m);
		printf("%lld\n",calc(n,m));
	}
}

【例题二】\(\gcd\) 求和

题目大意：给定你 \(n\)，试求：

\[\sum_{i=1}^n\sum_{j=1}^n(i,j) \]

其中 \(n\le 2\times10^6\)，这意味着 \(\mathcal{O}(n\sqrt n)\) 的复杂度将无法通过。

题目分析：我们可以试着继续整出来上题中那种 \([(i,j)=1]\) 的形式，方便我们求解。

首先，我们考虑去枚举 \(\gcd\) 的结果 \(d\)，变成如下形式：

\[\sum_{d=1}^n d\sum_{i=1}^n\sum_{j=1}^n[(i,j)=d] \]

经典结论：\((i,j)=d\Leftrightarrow (i/d,j/d)=1\)，套用到上式：

\[\sum_{d=1}^n d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}[(i,j)=1] \]

考虑故技重施，再用上一题的方法进行变形：

\[\begin{aligned} \sum_{d=1}^nd\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}[(i,j)=1] \\ \sum_{d=1}^nd\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}\sum_{k\mid (i,j)}\mu(k) \\ \sum_{d=1}^nd\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}\sum_{k\mid i\land k\mid j}\mu(k) \\ \sum_{d=1}^nd\sum_{k=1}^n\mu(k)(\frac{n}{dk})^2 \end{aligned} \]

分析下此时的复杂度，后面那个 \(\sum\) 可以预处理前缀和+除法分块，已经快了很多了，但仍为 \(\mathcal{O}(n\sqrt n)\)。

蛇皮操作之——改变枚举量，令 \(T=dk\)，先枚举 \(T\)，然后再变成：

\[\sum_{T=1}^n\sum_{d\mid T}d\mu(\frac{T}{d})(\frac{n}{T})^2 \]

由 \(\mu*id=\varphi\)，发现还可以继续化为：

\[\sum_{T=1}^n\varphi(T)(\frac{n}{T})^2 \]

显然可以线性筛出 \(\varphi\) 并求前缀和，然后上个除法分块就行了，这样最后的复杂度为 \(\mathcal{O}(n+\sqrt n)\)。

ll n,cnt,pri[N],phi[N],s[N];
bool isPrime[N];

void init(int n){
	memset(isPrime,1,sizeof(isPrime));
	isPrime[1]=0;phi[1]=1; 
	For(i,2,n){
		if(isPrime[i]) pri[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
			isPrime[i*pri[j]]=0;
			if(!(i%pri[j])){
				phi[i*pri[j]]=phi[i]*pri[j];
				break;
			}
			phi[i*pri[j]]=phi[i]*phi[pri[j]];
		}
	}
	For(i,1,n) s[i]=s[i-1]+phi[i];
}

ll calc(int n){
	ll res=0,r;
	for(int l=1;l<=n;l=r+1){
		r=n/(n/l);
		res+=(s[r]-s[l-1])*(n/l)*(n/l);
	}
	return res;
}

void Main(){
	read(n);init(n);
	printf("%lld",calc(n));
}

标签：frac,函数,积性,乌斯,sum,mid,mu,反演,莫比
From： https://www.cnblogs.com/los114514/p/17782964.html

相关文章

  • 快速莫比乌斯/沃尔什变换 (FMT/FWT)
    仅供学习。给定长度为\(2^n\)两个序列\(A,B\)，设\[C_i=\sum_{j\oplusk=i}A_j\timesB_k\]分别当\(\oplus\)是or,and,xor时求出\(C\)or\[c_{i}=\sum_{j|k\ini}a_{j}b_{k}\]定义\(fwt[a]_i=\sum_{j\ini}a_j\)显然$$\begin{aligned}fwt[a]\timesf......
  • 莫比乌斯反演 超级详细推导
    莫比乌斯反演今天是世纪性的一天，因为我又又又又来看数论且弄懂了qwq。前置知识:,(我们需要将式子化为整数分块可以解决的形式)莫比乌斯函数->函数构成当时,当,且为互异质数时,;(也就是就是分解质因数后，没有幂次大于2的质因子，此时函数值根据分解的个数决定)只要含有......
  • 莫比乌斯函数及反演学习笔记
    前置知识\(1.\)艾佛森括号：\([P]=\begin{cases}1&\mathtt{(if\P\is\true)}\\0&\mathtt{(otherwise)}\end{cases}\)\(2.\)\(a\midb\)表示\(a\)是\(b\)的因子\(3.\)整除分块：\(\displaystyle\sum_{i=1}^n\lfloor\dfrac{N}{i}\rfloor\......
  • 莫比乌斯反演 学习笔记
    前置知识整除分块把之前写的博客搬过来了模型求\(\large\sum^{n}_{i=1}\lfloor{\frac{n}{i}}\rfloor\)假设\(n\)等于10，我们可以列出下表：\(\i\)12345678910\(\frac{10}{i}\)10532211111如果我们的\(n\)更大时，我们可以发现\(\fra......
  • 莫比乌斯函数
    推荐视频：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.\]......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99