莫比乌斯反演

· · 个人记录

前言

本文章中所有出现的 [n=1] 表示只有 n=1时， [n=1] 为 1 ，否则为 0。

## 狄利克雷卷积 ### 引出： 我们都知道卷积的算式： $C(n)= \sum\limits_{i \oplus j = n} A(i) \times B(j)

如果 “ \oplus ”为加号，就是加法卷积，我们可以用 FFT， NTT 等算法来快速实现加法卷积。

那么现在我们令“ \oplus ”为乘号，它就成了乘法卷积。

C(n)= \sum\limits_{i \times j = n} A(i) \times B(j) \Leftrightarrow C(n)= \sum\limits_{i\mid n} A(i) \times B(\tfrac{n}{i})

上面这个就是狄利克雷卷积。

我们一般简写成： C= A * B，“*” 代表以上的运算。

它满足交换律：A * B = B * A

结合律：(A * B) * C = A * (B * C)

分配律：(A + B) * C = A * C + B * C

单位元：

我们有一个叫单位元的东西，单位元叫 \epsilon 。

对于任意一个数论函数 f ， 都有 \epsilon * f = f。

而单位元的求法为 \epsilon(n)=[n=1]= \begin{cases}1\quad n=1\\0\quad n>1\end{cases}；

逆元：

每一个数论函数都存在它的逆元。

现在有两个数论函数 f， g，g 为 f 的逆元，则有：f*g=\epsilon 。

求一个函数的逆：g(n)=\tfrac{1}{f(1)}\left([n=1]-\sum\limits_{i\mid n,i\ne1}f(i)g(\tfrac{n}{i})\right)

积性函数：

积性函数：当n \perp m时：

f(n\times m)=f(n)\times f(m)

常见积性函数：id ，\mu ，\phi ，\sigma。

$\sigma_0(n)$ 函数就是求 $n$ 的因数个数。 $\phi(n)$ 函数就是求与 $n$ 互质的个数。 为什么要这么强调积性函数呢？因为这种函数可以通过线性筛来快速求解得到。 ### 莫比乌斯反演： 我们定义 $1$ 的逆为 $\mu$ 。 定义：$1 * \mu = \epsilon$。 $1$ 的逆元为 $\mu$ 。 设一个函数 $f$ ， $f(n)=1$ 。 $\epsilon(n)=[n=1]=\sum\limits_{d\mid n}\mu(d)\times f(\tfrac{n}{d})=\sum\limits_{d\mid n}\mu(d)\times 1=\sum\limits_{d\mid n}\mu(d)

现在有两个数论函数 f 和 g ，满足 f * 1 = g ，那么有 g * \mu = f。

则有： f(n) = \sum\limits_{i \mid n} g(i) \times \mu(\tfrac{n}{i}) 。（莫比乌斯反演结论）

$\mu(n) = \begin{cases} (-1)^{t}\quad n = p_1p_2p_3...p_t且p_i互不相同。\\ 0\quad n不符合上述条件。\end{cases}

例题

例一

求：\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=1]\quad(n<m)

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

因为 d \mid gcd(i,j) 所以 d\mid i 且 d\mid j ，因此 i ， j 必须得是 d 的倍数，然后把 d 提前。

得：

\Leftrightarrow \sum\limits_{d=1}^n\mu(d)\times \left\lfloor\tfrac{n}{d}\right\rfloor\times \left\lfloor\tfrac{m}{d}\right\rfloor

首先 \mu 可以用线性筛求出，然后式子前面一部分可以用前缀和实现，可以用后面一部分可以通过分块思想实现。

时间复杂度：O(n) 。

例二

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

我们发现与例一相比，例二的 gcd(i,j) 的数不再是 1 ，但是如果满足 gcd(i,j)=k 的话，必有 k \mid i 且 k \mid j ，那么我们可以让他们同除 k ，得到例一的式子。

\sum\limits_{i=1}^{\left\lfloor \tfrac{n}{k} \right\rfloor} \sum\limits_{j=1}^{\left\lfloor \tfrac{m}{k} \right\rfloor} [gcd(i,j)=1] \sum\limits_{i=1}^{\left\lfloor \tfrac{n}{k} \right\rfloor} \sum\limits_{j=1}^{\left\lfloor \tfrac{m}{k} \right\rfloor} \sum\limits_{d \mid gcd(i,j)}\mu(d) \sum\limits_{d=1}^{\left\lfloor \tfrac{n}{k} \right\rfloor}\mu(d) \times {\left\lfloor \tfrac{n}{kd} \right\rfloor} \times {\left\lfloor \tfrac{m}{kd} \right\rfloor}

例三

求：\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)为素数]

例三我们现在的 gcd(i,j) 要求是为素数，我们可以枚举 k ，这样问题就转化成了例二。

\Leftrightarrow \sum\limits_{k=1}^n\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=k]\quad k为素数 \Leftrightarrow \sum\limits_{k=1}^n\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{m}{k}\right\rfloor}[gcd(i,j)=1]\quad k为素数 \Leftrightarrow \sum\limits_{k=1}^n\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{m}{k}\right\rfloor}\sum\limits_{d\mid gcd(i,j)}\mu(d)\quad k为素数 \Leftrightarrow \sum\limits_{k=1}^n \sum\limits_{d=1}^{\left\lfloor\tfrac{n}{k}\right\rfloor} \mu(d)\times \left\lfloor\tfrac{n}{kd}\right\rfloor \times \left\lfloor\tfrac{m}{kd}\right\rfloor\quad k为素数

如果你觉得这样子就是最简了，直接就枚举k，感觉可以，但是会超时。所以我们要继续对这个式子进行优化。我们设 T=kd ，得：

\Leftrightarrow \sum\limits_{k=1}^n \sum\limits_{dk=1}^n \mu(d)\times \left\lfloor\tfrac{n}{kd}\right\rfloor\times \left\lfloor\tfrac{m}{kd}\right\rfloor\quad k为素数 \Leftrightarrow \sum\limits_{T=1}^n \sum\limits_{d\mid T}\mu(\tfrac{T}{d}) \times \left\lfloor\tfrac{n}{T}\right\rfloor\times \left\lfloor\tfrac{m}{T}\right\rfloor \quad d为素数

然后 \sum\limits_{d \mid T} \mu(\tfrac{T}{d}) 也可以在线性筛中求解，只要枚举每一个素数，然后把所有可以整除它的都加上就行了。

例四

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

老套路，我们枚举 k。

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

这次同除 k 就要注意了，由于我们除 k 之后， i 和 j 都变小了，所以我们必须再乘回来。

\sum\limits_{k=1}^n\sum\limits_{i=1}^{\left\lfloor \tfrac{n}{k} \right\rfloor} \sum\limits_{j=1}^{\left\lfloor \tfrac{n}{k} \right\rfloor} i \times j \times k^3 \times [gcd(i,j)=1] \sum\limits_{k=1}^n\sum\limits_{i=1}^{\left\lfloor \tfrac{n}{k} \right\rfloor} \sum\limits_{j=1}^{\left\lfloor \tfrac{n}{k} \right\rfloor} i \times j \times k^3 \times \sum\limits_{d\mid gcd(i,j)}\mu(d) \sum\limits_{k=1}^n \sum\limits_{d=1}^{\left\lfloor \tfrac{n}{k} \right\rfloor}\mu(d) \times \sum\limits_{i=1}^{\left\lfloor \tfrac{n}{kd} \right\rfloor} \sum\limits_{j=1}^{\left\lfloor \tfrac{n}{kd} \right\rfloor} i \times j \times k^3 \times d^2 \sum\limits_{k=1}^n k^3 \times \sum\limits_{d=1}^{\left\lfloor \tfrac{n}{k} \right\rfloor}\mu(d) \times d^2 \times \sum\limits_{i=1}^{\left\lfloor \tfrac{n}{kd} \right\rfloor} \sum\limits_{j=1}^{\left\lfloor \tfrac{n}{kd} \right\rfloor} i \times j

设 T = kd ：

\sum\limits_{T=1}^n \sum\limits_{d\mid T}\mu(\tfrac{T}{d}) \times d \times T^2 \times \sum\limits_{i=1}^{\left\lfloor \tfrac{n}{T} \right\rfloor}i \sum\limits_{j=1}^{\left\lfloor \tfrac{n}{T} \right\rfloor}j \sum\limits_{T=1}^n T^2 \times \sum\limits_{d\mid T}\mu(\tfrac{T}{d}) \times d \times \left( \sum\limits_{i=1}^{\left\lfloor \tfrac{n}{T} \right\rfloor}i \right)^2

因为我们有 id * \mu = \phi ，所以 \phi(n) = \sum\limits_{i\mid n}\mu(\tfrac{n}{i}) \times i 。

\sum\limits_{T=1}^n T^2 \times \phi(T) \times \left( \sum\limits_{i=1}^{\left\lfloor \tfrac{n}{T} \right\rfloor}i \right)^2 ### 例五 求：$\sum\limits_{i1=L}^R\sum\limits_{i2=L}^R...\sum\limits_{in=L}^R[gcd(i1,i2...in)=K]

按照之前的套路。

\sum\limits_{i1=\left\lfloor\tfrac{L-1}{K}\right\rfloor+1}^{\left\lfloor\tfrac{R}{K}\right\rfloor}\sum\limits_{i2=\left\lfloor\tfrac{L-1}{K}\right\rfloor+1}^{\left\lfloor\tfrac{R}{K}\right\rfloor}...\sum\limits_{in=\left\lfloor\tfrac{L-1}{K}\right\rfloor+1}^{\left\lfloor\tfrac{R}{K}\right\rfloor}[gcd(i1,i2...in)=1] \sum\limits_{i1=\left\lfloor\tfrac{L-1}{K}\right\rfloor+1}^{\left\lfloor\tfrac{R}{K}\right\rfloor}\sum\limits_{i2=\left\lfloor\tfrac{L-1}{K}\right\rfloor+1}^{\left\lfloor\tfrac{R}{K}\right\rfloor}...\sum\limits_{in=\left\lfloor\tfrac{L-1}{K}\right\rfloor+1}^{\left\lfloor\tfrac{R}{K}\right\rfloor}\sum\limits_{d\mid gcd(i1,i2...in)}\mu(d) \sum\limits_{d=1}^{\left\lfloor\tfrac{R}{K}\right\rfloor}\mu(d)\times \left\lfloor\tfrac{\left\lfloor\tfrac{R}{K}\right\rfloor-\left\lfloor\tfrac{L-1}{K}\right\rfloor-1}{d}\right\rfloor^n

设 Y=\left\lfloor\tfrac{R}{K}\right\rfloor ， X = \left\lfloor\tfrac{L-1}{K}\right\rfloor + 1 。

\sum\limits_{d=1}^{\left\lfloor\tfrac{R}{K}\right\rfloor}\mu(d)\times \left\lfloor\tfrac{Y - X}{d}\right\rfloor^n

例六

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

我们可以通过枚举 k 把 gcd(i,j) 转到外面。

\sum\limits_{k=1}^n \sum\limits_{i=1}^n \sum\limits_{j=1}^m \sigma_1(k) \times [gcd(i,j)=k] \sum\limits_{k=1}^n \sum\limits_{i=1}^{\left\lfloor \tfrac{n}{k} \right\rfloor} \sum\limits_{j=1}^{\left\lfloor \tfrac{m}{k} \right\rfloor} \sigma_1(k) \times [gcd(i,j)=1] \sum\limits_{k=1}^n \sum\limits_{i=1}^{\left\lfloor \tfrac{n}{k} \right\rfloor} \sum\limits_{j=1}^{\left\lfloor \tfrac{m}{k} \right\rfloor} \sigma_1(k) \times \sum\limits_{d\mid gcd(i,j)}\mu(d) \sum\limits_{k=1}^n \sigma_1(k) \times \sum\limits_{d=1}^{\left\lfloor \tfrac{n}{k} \right\rfloor}\mu(d) \times \left\lfloor \tfrac{n}{kd} \right\rfloor \times \left\lfloor \tfrac{m}{kd} \right\rfloor

设 T=kd

\sum\limits_{T=1}^{n} \left\lfloor \tfrac{n}{T} \right\rfloor \times \left\lfloor \tfrac{m}{T} \right\rfloor \times \sum\limits_{d\mid T}\sigma_1(d) \times \mu(\left\lfloor \tfrac{T}{d} \right\rfloor) ### 例七 $\sum\limits_{i=1}^n \sum\limits_{j=1}^n gcd(A_i,A_j)

乍一看，我们发现我们对 Ai ， Aj 无从下手，我们希望把 gcd 里面的东西变成我们可以控制的。我们可以用 B 来统计 A 出现的次数， MAXA 表示 A 中最大的数的值，这样一来， gcd 里面的东西就是我们可以控制的 i 和 j 了。

\sum\limits_{i=1}^{MAXA} \sum\limits_{j=1}^{MAXA} gcd(i,j) \times B_i \times B_j \sum\limits_{k=1}^{MAXA} \sum\limits_{i=1}^{MAXA} \sum\limits_{j=1}^{MAXA} [gcd(i,j)=k] \times B_i \times B_j \sum\limits_{k=1}^{MAXA} \sum\limits_{i=1}^{\left\lfloor \tfrac{MAXA}{k} \right\rfloor} \sum\limits_{j=1}^{\left\lfloor \tfrac{MAXA}{k} \right\rfloor} [gcd(i,j)=1] \times B_{ik} \times B_{jk} \sum\limits_{k=1}^{MAXA} \sum\limits_{i=1}^{\left\lfloor \tfrac{MAXA}{k} \right\rfloor} \sum\limits_{j=1}^{\left\lfloor \tfrac{MAXA}{k} \right\rfloor} \sum\limits_{d\mid gcd(i,j)}\mu(d) \times B_{ik} \times B_{jk} \sum\limits_{k=1}^{MAXA} \sum\limits_{d=1}^{\left\lfloor \tfrac{MAXA}{k} \right\rfloor} \mu(d) \times \sum\limits_{i=1}^{\left\lfloor \tfrac{MAXA}{kd} \right\rfloor} \sum\limits_{j=1}^{\left\lfloor \tfrac{MAXA}{kd} \right\rfloor} B_{ikd} \times B_{jkd}

设 T=kd

\sum\limits_{k=1}^{MAXA} \sum\limits_{dk=1}^{MAXA} \mu(d) \times \sum\limits_{i=1}^{\left\lfloor \tfrac{MAXA}{kd} \right\rfloor} \sum\limits_{j=1}^{\left\lfloor \tfrac{MAXA}{kd} \right\rfloor} B_{ikd} \times B_{jkd} \sum\limits_{T = 1}^{MAXA} \sum\limits_{d \mid T} \mu(d) \times \sum\limits_{i=1}^{\left\lfloor \tfrac{MAXA}{T} \right\rfloor} \sum\limits_{j=1}^{\left\lfloor \tfrac{MAXA}{T} \right\rfloor} B_{iT} \times B_{jT} \sum\limits_{T = 1}^{MAXA} \sum\limits_{d \mid T} \mu(d) \times \left( \sum\limits_{i=1}^{\left\lfloor \tfrac{MAXA}{T} \right\rfloor} B_{iT} \right)^2