辣么多的芝士一天学废の莫比乌斯反演篇~

不知道隔壁小姐姐会不会来看?

莫比乌斯函数

定义

$$\mu(x)= \left\{ \begin{aligned} \quad &1 \qquad &(x=1) \\ \quad &(-1)^k \qquad &(x=\prod{p_i},\ p_i \in P,\ k=|P|) \\ \quad &0 \qquad &(other) \\ \end{aligned} \right.$$

大概就是:
如果$x$能被表示为若偶数个不同素数的积, $\mu(x)=+1$,$x=1$理解为$0$个素数;
如果$x$能被表示为若奇数个不同素数的积, $\mu(x)=-1$;
其他情况$\mu(x)=0$.

我们把它理解为一个容斥系数, 当我们在做一些有关素数的容斥时会用到.

一个性质

$$\sum_{d|n}{\mu(d)} \Leftrightarrow [n==1]$$

这个式子有一个比较巧妙的证明, 设$k$为$n$不同素因子的个数, 用二项式定理:

$$\begin{aligned} &\sum_{d|n}{\mu(d)} =\sum_{i=1}^{k}{(-1)^{i}C_{k}^{i}} =(1-1)^{k} =[n==1] \end{aligned}$$

求莫比乌斯函数[^1]

[^1]: 这里用到的是$O(N)$线性筛, 可能并不是那么优秀. (据说)对于一类数论函数求前缀和的问题, 杜教筛可以用做到低于线性的复杂度求解.

类似欧拉函数$\varphi$的容斥, 我们容易证明莫比乌斯函数$\mu$也是线性的, 尝试用线性筛预处理.
除去$x=1$的特殊情况, 我们可以得到一个显然的结论: 对于素数$p$有$\mu(p)=-1$.
每次在更新后面值的时候, $\mu(ip)=[i\ mod\ p > 0]* -\mu(i)$.

一个例题[HAOI2011]Problem b[^2]

[^2]: 网上普遍使用的是推式子的方式, 貌似没有这种方法劝退简单.

$i \in [a,b]$, $j \in [c,d]$. 问:有多少对$i,j$满足$(i,j)=k$.

我们发现这个问题可以转化为求有多少对$i,j$满足$(i,j)=1$($i \in [\lfloor \frac{a}{k} \rfloor,\lfloor \frac{b}{k} \rfloor]$, $j \in [\lfloor \frac{c}{k} \rfloor,\lfloor \frac{d}{k} \rfloor]$),

问题转化为:

$a \in [1,n]$, $b \in [1,m]$. 问:有多少对$a,b$满足$(a,b)=1$.

一个简单的想法: 容斥.
共有$nm$对数字, 容斥地处理每次某个素数集的倍数. 有奇数个素数则减去贡献, 有偶数个素数则补回贡献.
考虑使用莫比乌斯函数$\mu$作为容斥系数.

我们枚举因子$q$, 贡献就是区间内包含$q$的对数, 只有包含不重复素因子的才做贡献.

$$\sum_{i=1}^{min(n,m)}{\mu(i)\lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor}$$

最后用整除分块将式子优化到$O(\sqrt{N})$.

地理课累[^3]卷积

[^3]: 原文Dirichlet, 官译狄利克雷, 北爷译地理课累.

定义

定义$f(x)$和$g(x)$的Dirichlet卷积为: $$(f*g)(n)=\sum_{d|n}{f(d)g(\frac{n}{d})}$$

一些性质

• 交换律 $f*g=g*f$
• 结合律 $(f*g)*h=f*(g*h)$
• 分配律 $f*(g+h)=f*g+f*h$
• $\epsilon$$\epsilon(n) = \mu*1 = \sum_{d|n}{\mu(d)} = [n==1]$">^4为单位元, $f*\epsilon=f$

莫比乌斯反演

公式

对于两个数论函数$f(x)$, $g(x)$.

$$若f(n)=\sum_{d|n}{g(d)}, 有g(n)=\sum_{d|n}{\mu(\frac{n}{d})f(d)} \\ 若f(n)=\sum_{n|d}{g(d)}, 有g(n)=\sum_{n|d}{\mu(\frac{d}{n})f(d)}$$

证明$*$%E6%8C%87Dirichlet%E5%8D%B7%E7%A7%AF.">^5

第一种形式

原问题转化为已知$f=g*1$证明$g=f*\mu$.

利用上文中Dirichlet卷积的性质: $$\begin{aligned} f &= g*1 \\ f*\mu &= g*1*\mu \\ f*\mu &= g*\epsilon \\ g &= f*\mu \end{aligned}$$

证毕.

第二种形式^6

考虑逆推这个式子.

$$\begin{aligned} &\sum_{n|d}{\mu(\frac{d}{n})f(d)} \\ =& \sum_{k=1}^{+\infty}{\mu(k)f(kn)} = \sum_{k=1}^{+\infty}{\mu(k)\sum_{kn|d}{g(d)}} \\ =& \sum_{n|d}{g(d)\sum_{k|\frac{n}{d}}{\mu(k)}} = \sum_{n|d}{g(d)\epsilon(\frac{n}{d})} \\ =& g(n) \end{aligned}$$

我们把$d$表示为$kn$的形式, 然后把$f$的原定义代入式子.
发现枚举$k$再枚举$kn$的倍数可以转换为直接枚举$n$的倍数再求出$k$,
发现后面那一块其实就是$\epsilon$, $g*\epsilon=g$.

证毕.

一个例题[国家集训队]Crash的数字表格

题意即:

$$\sum_{i=1}^{n} \sum_{j=1}^{m} [i,j]$$

略微转化一下,得到: $$\sum_{d}^{min(n,m)}{ d* \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} \epsilon(gcd(i,j))*i*j }$$

把后面的式子单独拿出来算, $$\begin{aligned} f(a,b)=& \sum_{i=1}^{a} \sum_{j=1}^{b} \epsilon(gcd(i,j))*i*j \\=& \sum_{d=1}^{min(a,b)}{ \mu(d) \sum_{d|i}^{a} \sum_{d|j}^{b} i*j } \\=& \sum_{d=1}^{min(a,b)}{ \mu(d)*d^2 \sum_{i=1}^{\lfloor \frac{a}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{b}{d} \rfloor} i*j } \end{aligned}$$

发现后面这一块就是等差数列求和. $$g(a,b)= \sum_{i=1}^{a} \sum_{j=1}^{b} i*j = \sum_{i=1}^{a}{ i* \sum_{j=1}^{b} j } = \frac{a(b+1)a(b+1)}{4}$$

所以 $$f(a,b)= \sum_{d=1}^{min(a,b)} \mu(d)*d^2*g(\lfloor \frac{a}{d} \rfloor,\lfloor \frac{b}{d} \rfloor)$$ 可以整除分块.

原式化为 $$\sum_{d}^{min(n,m)} d*f(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)$$

可以整除分块.

整个式子比较麻烦, 应该尽量降低代码耦合度(分解出$f$跟$g$两个函数应该就没问题了).

一天学废系列预告:

Polya定理 简单概率期望DP&高斯消元随机游走概率期望