【数学】莫比乌斯反演

莫比乌斯函数

定义

设$n=\prod_{i=1}^{m}p_{i}^{k_{i}}$,则有

\mu(n)=
\begin{cases}
1 \quad \ \ & n=1\\
(-1)^{m} \quad \ \ & \prod_{i=1}^{m}k_{i}=1\\
0 \quad & otherwise(k_{i}>1)
\end{cases}

性质

莫比乌斯函数是积性函数
应用:根据这一性质,我们可以采取线性筛法,用$O(n)$的时间筛出$[1,n]$的莫比乌斯函数值。
代码:见这里

莫比乌斯函数

公式

如果$f(n),g(n)$是数论函数,且满足$f(n)=\sum_{d|n}g(d)$,则有莫比乌斯反演:

g(n)=\sum_{d|n}\mu(\frac{n}{d})f(d)=\sum_{d|n}\mu(d)f(\frac{n}{d})

应用

求$\gcd = k$的个数

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

设$f(k)$为$\gcd(i,j)=k$的个数,$g(k)$为满足$k|\gcd(i,j)$的对数,则有:

g(k)=\sum_{x=1}^{\lfloor\frac{n}{k}\rfloor}f(kx)

我们只需快速求出$g(k)$,可知,如果$i,j$能被$k$整除,那么它们可以写成$i = k\cdot x_1, j = k\cdot x_2$的形式,我们只需求有多少对$x_1,x_2$即可,可得:

g(k) = \left\lfloor\frac n k\right\rfloor\left\lfloor\frac m k\right\rfloor

根据莫比乌斯反演的变形,可求得$f(k)$:

\begin{aligned}f(k) &= \sum_{x = 1}^{\left\lfloor\frac n k\right\rfloor}\mu(x)g(k\cdot x)\\&=\sum_{x = 1}^{\left\lfloor\frac n k\right\rfloor}\mu(x)\left\lfloor\frac n {kx}\right\rfloor\left\lfloor\frac m {kx}\right\rfloor\end{aligned}

$\gcd(i,j)$的幂

\sum_{i = 1}^n\sum_{j = 1}^m\gcd(i, j)^k \bmod ({10}^9 + 7)

按照我们刚刚的技巧,枚举最大公约数$d$然后转换为可分块的形式:

\begin{aligned}\sum_{i = 1}^n\sum_{j = 1}^m\gcd(i, j)^k& = \sum_{d = 1}^nd^k\sum_{i = 1}^n\sum_{j = 1}^m[\gcd(i, j) = d]\\& = \sum_{d = 1}^nd^k\sum_{x=1}^{\left\lfloor\frac n d\right\rfloor}\mu(x)\left\lfloor\frac n {dx}\right\rfloor\left\lfloor\frac m {dx}\right\rfloor\end{aligned}

到这里可以分套分块$O((\sqrt n)^2) = O(n)$
后面还可以优化,后面再补。