莫比乌斯反演

· · 个人记录

莫比乌斯反演

\mu函数

定义：

性质：

  1. 对于任意正整数
\sum_{d | n}\mu(d) = \epsilon(n) \text{其中元函数} \epsilon \text{的定义为}\epsilon(n)\begin{cases}1,n=1\\0,n>1\end{cases}
  1. 对于任意正整数
\sum_{d | n}\frac{\mu(d)}{d} = \frac{\phi(n)}{n}

莫比乌斯反演定理

对于两个函数 F(n) 和 f(n)，若满足

F(n) = \sum_{d | n} f(d)

则有定理

f(n) = \sum_{d | n} \mu(d) F(\lfloor\frac{n}{d}\rfloor)

证明

\sum_{d | n} \mu(d) F(\lfloor\frac{n}{d}\rfloor) = \sum_{d | n}\mu(d)\sum_{i | \lfloor\frac{n}{d}\rfloor}f(i) \ \text{(代入)} = \sum_{d | n}\sum_{i | \lfloor\frac{n}{d}\rfloor}\mu(d)f(i) \ \text{(把}\mu(d)\text{带进内层}\sum_{i | \lfloor\frac{n}{d}\rfloor}\text{中)}

这个式子等价于

= \sum_{i | n}\sum_{d | \lfloor\frac{n}{i}\rfloor}\mu(d)f(i) = \sum_{i | n}f(i)\sum_{d | \lfloor\frac{n}{i}\rfloor}\mu(d) \ \text{(把f(i)提出来)}

因为 \mu 函数有性质

\sum_{d | n} \mu(d) = \epsilon(n)

所以

= f(n)

Q.E.D

例题

  1. 求
\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]\ \ (n < m) \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]\ \ (n < m) = \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\mu(d) \sum_{d=1}^{n}\mu(d)\times\lfloor\frac{n}{d}\rfloor\times\lfloor\frac{m}{d}\rfloor

使用整除分块，时间复杂度可以优化到 O(\sqrt{n})。

  1. 求
\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k]\ \ (n < m) \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k] = \sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]

等同于例一。

  1. 求
\sum_{i=1}^{n}\sum_{j=1}^{m}i\times j\times [gcd(i,j)=k]\ \ (n < m) \sum_{i=1}^{n}\sum_{j=1}^{m}i\times j\times [gcd(i,j)=k]

仍然是变成 [gcd(i,j)=1] 的形式，但要考虑 i\times j 的贡献。

因为 i 和 j 同时缩小了 k 倍，所以 i\times j 产生的贡献缩小了 k^2 倍。

= \sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}i\times j\times k^2 \times[gcd(i,j)=1] = \sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}i\times j\times k^2 \times\sum_{d|gcd(i,j)}\mu(d) = k^2\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\times d^2\sum_{i=1}^{\lfloor\frac{n}{dk}\rfloor}i\sum_{j=1}^{\lfloor\frac{m}{dk}\rfloor}j

后面两个和式是等差数列。

时间复杂度 O(\sqrt{n})。

  1. 求

\lfloor\frac{n}{d}\rfloor

\sum_{i=1}^{n}\sum_{j=1}^{m} lcm(i,j)\ \ (n < m) \sum_{i=1}^{n}\sum_{j=1}^{m} lcm(i,j)

代入公式 lcm(i,j)=\frac{i\times j}{gcd(i,j)}

= \sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i\times j}{gcd(i,j)} = \sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i\times j}{d}\times[gcd(i,j)=d] = \sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\frac{i\times j}{d}\times d^2 \times [gcd(i,j)=1] = \sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i\times j\times d\sum_{k|gcd(i,j)}\mu(k) = \sum_{d=1}^{n}\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\times d \times k^2\sum_{i=1}^{\lfloor\frac{n}{dk}\rfloor}i\sum_{j=1}^{\lfloor\frac{m}{dk}\rfloor}j

至此，这个式子已经是 O(n) 的复杂度了。

可以继续优化。