莫比乌斯反演

_Luminous · 2025-02-17 20:57:05 · 算法·理论

应用

较难求 f(n)，但是容易求出其倍数和或约数和 g(n)，就可以通过莫反来简化运算，求出 f(n)。

莫比乌斯函数

• d=p_1\times p_2\times...\times p_k$，其中 $k$ 为互异质因数，$\mu(d)=(-1)^k
• 其他情况（质因数的指数 \ge 2），\mu(d)=0

重要性质：n=1 时，\sum\limits_{d|n}\mu(d)=1；n\ne1时，\sum\limits_{d|n}\mu(d)=0。

即 \sum\limits_{d|n}\mu(d)=\epsilon(n)，\mu * 1=\epsilon。

注：这个性质意味着，莫比乌斯函数在狄利克雷生成函数中，等价于黎曼函数 \zeta 的倒数。所以在狄利克雷卷积中，莫比乌斯函数是常数函数 1 的逆元。

形式

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

• 形式一：如果有 f(n)=\sum\limits_{d|n}g(d)，那么有 g(n)=\sum\limits_{d|n}f(\frac{n}{d})\times\mu(d)

• 形式二：如果有 f(n)=\sum\limits_{n|d}g(d)，那么有 g(n)=\sum\limits_{n|d}f(d)\times\mu(\frac{n}{d})

经典例子

求 \sum\limits_{i=x}^{n}\sum\limits_{j=y}^{m}[\gcd(i,j)=k]

可以把原式划分成 4 块来处理，每一块式子形式为 \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=k]。

考虑化简，变成 \sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1]。

因为 \gcd(x,y)=1 时猜对答案做贡献，所以可以将其替换为 \epsilon(\gcd(i,j))，原式化为 \sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}\epsilon(\gcd(i,j))。

将 \epsilon 函数展开得到 \sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum\limits_{d|\gcd(i,j)}\mu(d)。

交换求和顺序，先枚举 d|\gcd(i,j) 可以得到 \sum\limits_{d=1}\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}[d|i]\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}[d|j]。

易知 1 ~ \lfloor\frac{n}{k}\rfloor 中 d 的倍数有 \lfloor\frac{n}{kd}\rfloor 个，故原式化为 \sum\limits_{d=1}^{\min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor。

接下来就可以整数分块求解了。