莫比乌斯反演

约 1130 个字 32 行代码 预计阅读时间 4 分钟

莫比乌斯函数

常数函数 $1$ 的狄利克雷逆，称之为莫比乌斯函数 $μ$

$μ(n)=\begin{cases}1&n=1\\ (-1)^m&n=p_1p_2…p_m\\ 0&otherwise\end{cases}$

其中$p_1，p_2，…，p_m$是各不相同的质数， 所以当$n$存在一个质因数次数$\ge2$，$μ(n)=0$

莫比乌斯反演公式

因数形式：
$g(n)=\sum\limits_{d\mid n} f(d) ⇔ f(n)=\sum\limits_{d\mid n} μ(d)\times g(n/d)$
狄利克雷卷积形式：
$g=f*1 ⇔ f=g*u$
倍数形式：
$g(n)=\sum\limits_{n\mid N} f(N) ⇔ f(n)=\sum\limits_{n\mid N} g(N)\times μ(N/n)$

这类题目是把看起来只能暴力算的式子化成数论分块可以算出来的东西
难度主要是推式子，式子不唯一，只要复杂度够低就行
证明很重要，证明就是教你怎么推式子
为了描述方便，$[n]$ 表示条件 $n$ 为真时为1，否则为0

重要结论

给定一个函数 $f$，$g$ 满足 $f=1*g$

$\sum\limits_{i=1}^n\sum\limits_{j=1}^m f(gcd(i,j))=\sum\limits_{d=1}^{min(n,m)} g(d)\lfloor\frac nd\rfloor\lfloor\frac md\rfloor$

解题步骤

1. 将 $f$ 替换成题目所给具体函数
2. 预处理 $g$，$g=\mu*f$
3. 数论分块计算

卷积证明

枚举gcd

$\sum\limits_{d=1}^{min(n,m)} f(d) \sum\limits_{i=1}^n\sum\limits_{j=1}^m [gcd(i,j)=d]$

i,j枚举d的倍数

$\sum\limits_{d=1}^{min(n,m)} f(d) \sum\limits_{i=1}^{\lfloor\frac nd\rfloor}\sum\limits_{j=1}^{\lfloor\frac md\rfloor} [gcd(i,j)=1]$

$\mu * 1=\epsilon$

$\sum\limits_{d=1}^{min(n,m)} f(d) \sum\limits_{i=1}^{\lfloor\frac nd\rfloor}\sum\limits_{j=1}^{\lfloor\frac md\rfloor} \sum\limits_{t\mid gcd(i,j)}\mu(t)$

枚举 t

$\sum\limits_{d=1}^{min(n,m)} f(d) \sum\limits_{t=1}^{min(\lfloor\frac nd\rfloor,\lfloor\frac md\rfloor)} \mu(t)\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}\sum\limits_{j=1}^{\lfloor\frac md\rfloor} [t\mid gcd(i,j)]$

i,j枚举t的倍数

$\sum\limits_{d=1}^{min(n,m)} f(d) \sum\limits_{t=1}^{min(\lfloor\frac nd\rfloor,\lfloor\frac md\rfloor)} \mu(t)\sum\limits_{i=1}^{\lfloor\frac n{dt}\rfloor}\sum\limits_{j=1}^{\lfloor\frac m{dt}\rfloor} 1$

$\sum\limits_{d=1}^{min(n,m)} f(d) \sum\limits_{t=1}^{min(\lfloor\frac nd\rfloor,\lfloor\frac md\rfloor)} \mu(t)\lfloor\frac n{dt}\rfloor\lfloor\frac m{dt}\rfloor$

设 $T=dt$

$\sum\limits_{T=1}^{min(n,m)} \lfloor\frac nT\rfloor\lfloor\frac mT\rfloor \sum\limits_{d\mid T} f(d)\mu(T/d)$

发现 $\sum\limits_{d\mid T} f(d)\mu(T/d)$ 可以表示为 $g(T)=f*\mu$

$\sum\limits_{T=1}^{min(n,m)} g(T)\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor$

莫反证明

$f=1*g$

$\sum\limits_{i=1}^n\sum\limits_{j=1}^m \sum\limits_{d\mid gcd(i,j)} g(d)$

枚举 $d$

$\sum\limits_{d=1}^{\min(n,m)} g(d) \sum\limits_{i=1}^n\sum\limits_{j=1}^m [d\mid gcd(i,j)]$

i,j枚举 $d$ 的倍数

$\sum\limits_{d=1}^{min(n,m)} g(d)\lfloor\frac nd\rfloor\lfloor\frac md\rfloor$

预处理

若 $f$ 是积性函数，则可以线性筛预处理(卷积性质4)，否则至少 $O(n\log\log n)$

void get_g_1(int N, const int *f, int *g)
{
    for (int i = 1; i <= N; i++)
        g[i] = 0;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; i * j <= N; j++)
            g[i * j] = (g[i * j] + mu[i] * f[j]) % mod;
    }
} // 依照卷积定义，O(nlogn)

void get_g_2(int N, const int *f, int *g)
{
    for (int i = 1; i <= N; i++)
        g[i] = f[i];
    for (int i = 1; i <= N; i++)
    {
        for (int j = 2; i * j <= N; j++)
            g[i * j] = (g[i * j] - g[i]) % mod;
    }
} // 类似求狄利克雷卷积逆的方式，不需要线性筛 mu ，O(nlogn)

void get_g_3(int N, const int *f, int *g)
{
    for (int i = 1; i <= N; i++)
        g[i] = f[i];
    for (int i = 0; i < prime_count; i++)
    {
        for (int j = N / prime[i]; j >= 1; j--)
            g[j * prime[i]] = (g[j * prime[i]] - g[j]) % mod;
    }
} // Magic! O(nloglogn)

最后一种可以理解成 DP: $g_{i,n}=\sum\limits_{d\mid n,d只含前i种质因子} \mu(d)f(n/d)$ 具体转移就是 $g_{i,n}=\begin{cases}g_{i-1,n}&p_i\nmid n\\ g_{i-1,n}-g_{i-1,n/p_i}&p_i\mid n\end{cases}$

大部分题目第二种就够用，不排除currywoe没遇到毒瘤题（bushi

例题

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

显然 $f=ε$，那么 $g=\mu$

---

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

显然 $f(x)=[x=k]$，稍微推一下式子，则 $g=\mu$

---

求 $\sum\limits_{p∈prime}\sum\limits_{i=1}^n \sum\limits_{j=1}^m [gcd(i,j)=p]$

显然 $f(x)=[x∈prime]$,那么 $g=\sum\limits_{d\mid x} \mu(x/d)[d∈prime]$

换种写法就是 $g(x)=\sum\limits_{p∈prime,p\mid x} μ(x/p)$

此题特殊之处，可以线性筛处理出 $g$

$g(x=i*p)=\begin{cases}1&i=1\\μ(i)&i\mod p=0\\μ(i)-g(i)&i\mod p\neq 0\end{cases}$

---

$\sum\limits_{i=1}^n \sum\limits_{j=1}^m gcd(i,j)$

显然 $f=id$，则 $g=φ$

---

变形：求 $\sum\limits_{i=1}^n \sum\limits_{j=1}^m ij\times gcd(i,j)$

参考答案 $=\sum\limits_{d=1}^{\min(n,m)} φ(d)*d^2*g(\lfloor\frac nd\rfloor)*g(\lfloor\frac md\rfloor)$

$g(x)=(1+x)*x/2$

---

变形：$\sum\limits_{i=1}^n \sum\limits_{j=1}^m lcm(i,j)$

参考答案 $=\sum\limits_{d=1}^{min(n,m)} d*sum(\lfloor\frac nd\rfloor,\lfloor\frac md\rfloor)$

$sum(n,m)=\sum\limits_{d=1}^{min(n,m)} μ(d)*d^2*g(\lfloor\frac nd\rfloor,\lfloor\frac md\rfloor)$

$g(n,m)=[(n+1)n/2]*[(m+1)*m/2]$

---

强烈推荐使用latex来推公式，下面为简要语法，更详细的见这里

$ $是行内公式

求和 \sum

下标 _{}

上标 ^{}

把限制写到上下 \limits

求积 \prod

分数 \frac{}{}

向下取整 \lfloor \rfloor

向上取整 \lceil \rceil

自动调整大小括号 \left( \right)

莫比乌斯函数 \mu

欧拉函数 \phi

乘法（和卷积区分） \times

开方，根号 \sqrt{} \sqrt[n]{}

属于，不属于 \in \notin