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

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

莫比乌斯函数

定义

$$ \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} $$

求莫比乌斯函数¹

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

一个例题[[HAOI2011]Problem b](https://www.luogu.com.cn/problem/P2522)²

$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})$.

地理课累³卷积

定义

定义$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$⁴为单位元, $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)} $$

证明⁵

第一种形式

原问题转化为已知$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} $$

证毕.

第二种形式⁶

考虑逆推这个式子.

$$ \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的数字表格](https://www.luogu.com.cn/problem/P1829)

题意即:

$$ \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&高斯消元随机游走概率期望