莫比乌斯函数

由欧拉函数过来

莫比乌斯函数的定义，设 $n$ 是一个合数，$p_1$ 是 $n$ 的最小质因子，

$n^{\prime }=\frac{n}{p_1}$，有：

若 $n$ 是质数，有 $\mu (n)=-1$。

即：

莫比乌斯反演

${\displaystyle f(n)=\sum _{d|n}g(d)\leftrightarrow g(n)=\sum _{d|n}\mu (d)f\left(\frac{n}{d}\right)}$

$f(n),g(n)$ 均为积性函数，$f(n)$ 称为 $g(n)$ 的莫比乌斯变换，$g(n)$ 称为 $f(n)$ 的莫比乌斯逆变换

练习

• P1829 Crash的数字表格 / JZPTAB
  求 ${\displaystyle \sum _{i=1}^n\sum _{j=1}^{m}lcm(i,j)mod20101009}$

• P 2522 [HAOI 2011] Problem b - 洛谷 | 计算机科学教育新生态
  求 ${\displaystyle \sum _{i=x}^n\sum _{j=y}^m[gcd(i,j=k)]}$

• LCMSUM
  求 ${\displaystyle \sum _{i=1}^{n}lcm(i,n)}$

• LibreOJ
  求 ${\displaystyle \sum _{i=1}^n\sum _{j=1}^{m}d(i,j)}$