莫比乌斯反演学习笔记

标签：limits 乌斯 sum mid mu 反演 莫比

莫比乌斯函数

定义

\[\mu(n) = \begin{cases} 1 & n = 1 \\ 0 & n\text{ 含有平方因子} \\ (-1)^k & \text{其中 }k\text{ 为 }n\text{ 本质不同的质因子个数} \end{cases} \]

性质

莫比乌斯函数是积性函数。

\[\sum\limits_{d \mid n} \mu(d) = \varepsilon(n) \\ \mu * 1 = \varepsilon \]

其中 \(\varepsilon(n) = [n = 1], 1(n) = 1\)。\(*\) 表示卷积。

证明：

设 \(n = \sum\limits_{i=1}^k {p_i}^{e_i}, n' = \sum\limits_{i=1}^k p_i\)。

则有

\[\sum\limits_{d \mid n} \mu(d) = \sum\limits_{d \mid n'} \mu(d) = \sum\limits_{i=0}^k \binom{k}{i} \cdot (-1)^i = \sum\limits_{i=0}^k \binom{k}{i} \cdot (-1)^i \cdot 1^{k-i} = (-1 + 1)^k = [n = 1] \]

补充结论：

\[\sum\limits_{d \mid \gcd{i,j}} \mu(d) = [\gcd(i,j) = 1] \]

显然。

线性求莫比乌斯函数

由于莫比乌斯函数是积性函数，故可以用线性筛求。

具体实现如下：

mu[1]=1；
for (int i=2;i<=n;i++) {
    if (!f[i]) prime[++cnt]=i,mu[i]=-1;
    for (int j=1;j<=cnt&&prime[j]*i<=n;j++) {
        f[prime[j]*i]=1;
        if (i%prime[j]==0) {
            mu[prime[j]*i]=0;
            break;
        } else mu[prime[j]*i]=-mu[i];
    }
}

莫比乌斯反演

设 \(f(n), g(n)\) 为两个数论函数。

形式一：

\[f(n) = \sum\limits_{d \mid n} g(d) \Rightarrow g(n) = \sum\limits_{d \mid n} \mu(d) f(\dfrac{n}{d}) \]

这种形式下， \(f(n)\) 被称为 \(g(n)\) 的莫比乌斯变换，\(g(n)\) 被称为 \(f(n)\) 的莫比乌斯反演。

容易发现当 \(f(n) = \varepsilon(n), g(n) = \mu(n)\) 时满足这个结论。

形式二：

\[f(n) = \sum\limits_{n \mid d} g(d) \Rightarrow g(n) = \sum\limits_{n \mid d} \mu(\dfrac{d}{n}) f(d) \]

例题

洛谷P2522 [HAOI2011]Problem b

每个区间左右端点都 \(\div k\)，然后就变成了求 \(\gcd(x, y) = 1\)。

然后是经典 Trick 拆成四个类似的式子，然后推导以下：

\[\sum\limits_{x=1}^n \sum\limits_{y=1}^m [\gcd(x, y) = 1] \\ = \sum\limits_{x=1}^n \sum\limits_{y=1}^m \sum\limits_{d \mid \gcd(x,y)} \mu(d) \\ = \sum\limits_{d=1}^{\min(n,m)} \mu(d) \sum\limits_{x=1}^n [d \mid x] \sum\limits_{y=1}^m [d \mid y] \\ = \sum\limits_{d=1}^{\min(n,m)} \mu(d) \lfloor\dfrac{n}{d}\rfloor \lfloor\dfrac{m}{d}\rfloor \]

然后数论分块优化一下即可。

标签：limits,乌斯,sum,mid,mu,反演,莫比
From： https://www.cnblogs.com/mk-oi/p/mobius.html