莫比乌斯反演学习笔记


莫比乌斯反演

数论函数

定义域为正整数的函数称为数论函数。

积性函数

如果 \(\forall a,b, (a,b)=1,f(ab)=f(a)f(b)\) ,这样的数论函数称为积性函数。

常见的数论函数:

  • 欧拉函数(如果 \((a,b)=1\) ,则有 \(\varphi(ab)=\varphi(a)\varphi(b)\))
  • 莫比乌斯函数
  • 除数函数 ,用 \(d_k(n)\) 表示。其值等于所有 \(n\) 的因子的 \(k\) 次方之和。

完全积性函数

如果 \(\forall a,b,f(ab)=f(a)f(b)\) ,这样的数论函数称为完全积性函数。

常见的完全积性函数有:

  • \(f(x)=e^x\)
  • \(f(x)=x\)

Dirichlet 卷积

两个数论函数 \(f,g\) 的 Dirichlet 卷积为: \((f*g)(n)=\sum _{d|n}f(d)g(\frac{n}{d})\) 。

其中 Dirichlet 卷积的单位元定义为 \(e\) ,且 \(e(n)=e(n)=\left\{\begin{matrix}
1\; (n=1)\\
0\; (n\neq 1)
\end{matrix}\right.\)

【结论】如果 \(f,g\) 均为积性函数,则 \(f*g\) 也为积性函数。

莫比乌斯函数

如果 \(n\) 含有平方因子,那么 \(\mu (n)=0\) ;否则 \(\mu(n)=(-1)^k\) ,其中 \(k\) 为 \(n\) 的本质不同的质因子个数。

【性质】\(e(n)=\sum _{d|n}\mu(d)\) .

【证明】我们令 \(n=\prod p_i^{q_i},n’=\prod p_i\) 。

显然,枚举 \(n\) 的因子和枚举 \(n’\) 因子的差异就在于少枚举了含有平方因子的因子。

则有 \(\sum _{d|n}\mu(d)=\sum _{d|n’}\mu(d)\) 。

此时的 \(d\),我们就可以考虑在 \(p_1,p_2,\cdots p_k\) 中任意选取组成一个因子了,于是就有 \(\sum _{d|n’}\mu(d)=\sum_{i=0}^k \begin{pmatrix} k\\i\end{pmatrix}(-1)^i=\sum_{i=0}^k \begin{pmatrix}k\\i\end{pmatrix}(-1)^i\cdot 1^{(k-i)}=(-1+1)^k=0^k\) 。

也就是只有当 \(k=0\) 的时候 \(\sum _{d|n}\mu(d)=1\) ,其他时候 \(\sum _{d|n}\mu(d)=0\) 。

而显然当 \(k=0\) 的时候,\(n=1\) ,于是就证明了。

莫比乌斯反演

设 \(f(n),g(n)\) 是两个数论函数,如果有 \(f(n)=\sum_{d|n} g(d)\) ,那么有 \(g(n)=\sum_{d|n}f(d)\mu (\frac{n}{d})\) 。

【证明】因为我们有 \(e=\mu *1\) ,而 \(f(n)=\sum_{d|n} g(d)\) 其实就是 \(f=g*1\) 。

于是 \(\mu*f=g*1*\mu=g*(1*\mu)=g*e=g\) 即 \(g=f*\mu\) 也就是 \(g(n)=\sum_{d|n}f(d)\mu (\frac{n}{d})\) 。

不过一般情况下构造一个 \(f(n)=\sum_{d|n} g(d)\)  形式的式子是比较难的,一般情况下我们会直接化成 \([gcd(i,j)=1]\) 的形式,然后通过 \(\sum_{d|gcd(i,j)}\mu(d)\) 来计算。

一种比较常见的问题是这样的:求 \(\sum _{i=1}^n\sum_{j=1}^mf(gcd(i,j))(n\le m)\) .

我们考虑枚举 \(gcd(i,j)\) 的结果,假设 \(d=gcd(i,j)\) ,于是就有 \(\sum _{i=1}^n\sum_{j=1}^mf(gcd(i,j))\\=\sum _{d=1}^n\sum _{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}f(d)[gcd(i,j)=1]\)

考虑将 \([gcd(i,j)=1]\) 部分反演,则有 \(\sum _{d=1}^n\sum _{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}f(d)[gcd(i,j)=1]\\=\sum _{d=1}^n\sum _{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}f(d)\sum_{d’|gcd(i’,j’)}\mu(d’)\\ =\sum  _{d=1}^n\sum_{d’=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\mu(d’) f(d)\left \lfloor \frac{n}{dd’} \right \rfloor \left \lfloor \frac{m}{dd’} \right \rfloor\)

我们令 \(g(T)=\sum_{d|T}f(d)\mu(\frac{T}{d})=f*\mu\)

则有 \(\sum _{i=1}^n\sum_{j=1}^mf(gcd(i,j))=\sum _{T=1}^ng(T)\left \lfloor \frac{n}{T} \right \rfloor \left \lfloor \frac{m}{T} \right \rfloor\)

【例9】HAOI2011 Problemb

【HAOI2011】Problem b

【例10】SPOJ5971 LCMSUM

【SPOJ】LCM Sum

【例11】hdu4944 FSF’s game

【HDU4944】FSF’s game

【例12】BZOJ3601 一个人的数论

【湖北省队互测】一个人的数论

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 61,992

Categories

Archive

Comments