莫比乌斯反演

对于正整数 $n$，有

其中 $[\cdot ]$ 是 Iverson 括号．

令 $n=\prod _{i=1}^k{p}_i^{e_i}$，设 $n^{\prime }=\prod _{i=1}^k{p}_i$．根据 二项式定理，有

$$\sum _{d\mid n}\mu (d)=\sum _{d\mid n^{\prime }}\mu (d)=\sum _{i=0}^k(\genfrac{}{}{0ex}{}{k}{i})(-1{)}^i=(1+(-1){)}^k=[k=0]=[n=1].$$

设 $f(n),g(n)$ 是两个数论函数．那么，有

$$f(n)=\sum _{d\mid n}g(d)⟺g(n)=\sum _{d\mid n}\mu \left(\frac{n}{d}\right)f(d).$$

直接验证，有：

式子变形的关键在于交换求和次序，并注意到 $k\mid d\mid n$ 就等价于 ${\displaystyle \frac{n}{d}}\mid {\displaystyle \frac{n}{k}}$．倒数第二个等号相当于对 ${\displaystyle \frac{n}{k}}$ 的因子 ${\displaystyle \frac{n}{d}}$ 处的莫比乌斯函数求和，所以就等于 $[{\displaystyle \frac{n}{k}}=1]$．这一表达式仅在 $n=k$ 处不是 $0$，最后就会得到 $g(n)$．

利用 Dirichlet 卷积，命题等价于

$$f=1\ast g⟺g=\mu \ast f.$$

利用 $1\ast \mu =\epsilon$，在左式的等号两侧同时对 $\mu$ 做卷积，就得到

$$f\ast \mu =(1\ast g)\ast \mu =(1\ast \mu )\ast g=\epsilon \ast g=g.$$

附：$\mathrm{\Lambda }(n)$ 表达式的证明

对于素数幂 $n=p^e(e\in {\mathbf{N}}_{+})$，有

$$\mathrm{\Lambda }(n)=\sum _{i=0}^e\mu (p^{e-i})\log p^i=\log p^e-\log p^{e-1}=\log p.$$

对于 $n=1$，显然有 $\mathrm{\Lambda }(n)=\log 1=0$．对于其他合数 $n$，有

$$\mathrm{\Lambda }(n)=\sum _{d\mid n}\mu (d)(\log n-\log d)=(\sum _{d\mid n}\mu (d))\log n-\sum _{d\mid n}\mu (d)\log d.$$

根据莫比乌斯函数的性质，$\log n$ 一项的系数为 $[n=1]=0$．对于后面的一项，可以进一步将 $d$ 分解为素因数之积．对于任何素数 $p\mid n$，考察 $\log p$ 的系数，都有：

$$-\sum _{p\mid d\mid n}\mu (d)=\sum _{(d/p)\mid (n/p)}\mu \left(\frac{d}{p}\right)=[\frac{n}{p}=1]=0.$$

由此，对于不止一个素因子的合数 $n$，都有 $\mathrm{\Lambda }(n)=0$．

设 $f(n),g(n)$ 是两个数论函数．那么，有

$$f(n)=\sum _{n\mid d}g(d)⟺g(n)=\sum _{n\mid d}\mu \left(\frac{d}{n}\right)f(d).$$

直接验证，有：

这和基本形式的推导完全对偶．

设 $f(n),g(n)$ 是两个数论函数．那么，有

$$f(n)=\prod _{d\mid n}g(d)⟺g(n)=\prod _{d\mid n}f(d{)}^{\mu (n/d)}.$$

直接验证，有：

其中，$a\uparrow b=a^b$ 是 Knuth 箭头．对比基本形式的证明可以发现，唯一的区别就是加法换成了乘法，且乘法换成了取幂．

设 $f(n),g(n),\alpha (n)$ 都是数论函数，且 ${\alpha }^{-1}(n)$ 是 $\alpha (n)$ 的 Dirichlet 逆，即

$$[n=1]=\sum _{d\mid n}\alpha \left(\frac{n}{d}\right){\alpha }^{-1}(d).$$

那么，有

$$f(n)=\sum _{d\mid n}\alpha \left(\frac{n}{d}\right)g(d)⟺g(n)=\sum _{d\mid n}{\alpha }^{-1}\left(\frac{n}{d}\right)f(d).$$

直接验证，有：

和基本形式的证明相比较，只需要将倒数第二个等号替换成 Dirichlet 逆的定义式．

设 $f(n),g(n)$ 是数论函数，且 $t(n)$ 是完全积性函数．那么，有

$$f(n)=\sum _{d\mid n}t\left(\frac{n}{d}\right)g(d)⟺g(n)=\sum _{d\mid n}\mu \left(\frac{n}{d}\right)t\left(\frac{n}{d}\right)f(d).$$

只需要验证对于完全积性函数 $t(n)$，它的 Dirichlet 逆就是 $\mu (n)t(n)$．直接验证，有：

$$\sum _{d\mid n}\mu (d)t(d)t\left(\frac{n}{d}\right)=\sum _{d\mid n}\mu (d)t(n)=t(n)[n=1]=[n=1].$$

最后一步用到了 $t(1)=1$．这对于 完全积性函数 是成立的．

设 $F(x)$ 和 $G(x)$ 都是 $[1,+\mathrm{\infty })$ 上的复值函数．那么，有

$$F(x)=\sum _{n=1}^{\lfloor x\rfloor }G\left(\frac{x}{n}\right)⟺G(x)=\sum _{n=1}^{\lfloor x\rfloor }\mu (n)F\left(\frac{x}{n}\right).$$

不妨对 $F$ 和 $G$ 补充定义，设当 时，恒有 $F(x)=G(x)=0$．那么，命题就等价于：

$$F(x)=\sum _{n}G\left(\frac{x}{n}\right)⟺G(x)=\sum _n\mu (n)F\left(\frac{x}{n}\right).$$

这些求和式都是对 $n\in {\mathbf{N}}_{+}$ 求和．

直接验证，有：

其中，为得到第二个等号，需要令 $k=nd$．

设 $f(n),g(n)$ 是数论函数．那么，有

$$f(n)=\sum _{k=1}^{n}g\left(\lfloor \frac{n}{k}\rfloor \right)⟺g(n)=\sum _{k=1}^n\mu (k)f\left(\lfloor \frac{n}{k}\rfloor \right).$$

只需要取 $F(x)=f(\lfloor x\rfloor )$ 和 $G(x)=g(\lfloor x\rfloor )$ 即可．

根据容斥原理，原式可以分成 $4$ 块来处理，且每一块的式子都具有形式

$$f(n,m,k)=\sum _{i=1}^n\sum _{j=1}^m[gcd(i,j)=k].$$

对于这类式子，接下来是一段标准的推导流程：提取公因数，应用莫比乌斯函数性质，交换求和次序．

首先，由于 $i,j$ 都只能取 $k$ 的倍数，可以先将这个因子提出来——这相当于代入 $i=k{i}^{\prime }$ 和 $j=k{j}^{\prime }$，就得到：

$$f(n,m,k)=\sum _{i=1}^{\lfloor n/k\rfloor }\sum _{j=1}^{\lfloor m/k\rfloor }[gcd(i,j)=1].$$

再利用莫比乌斯函数的性质可知：

$$[gcd(i,j)=1]=\sum _{d\mid gcd(i,j)}\mu (d)=\sum _d[d\mid i][d\mid j]\mu (d).$$

将它代入表达式，并交换求和次序，就得到：

$$f(n,m,k)=\sum _d\mu (d)(\sum _{i=1}^{\lfloor n/k\rfloor }[d\mid i])(\sum _{j=1}^{\lfloor m/k\rfloor }[d\mid j]).$$

这样一段操作的好处是，固定 $d$ 时，求和式中关于 $i$ 和 $j$ 的项相互分离，可以分别求和．接下来，因为

$$\sum _{i=1}^{\lfloor n/k\rfloor }[d\mid i]=\lfloor \frac{\lfloor n/k\rfloor }{d}\rfloor ,\sum _{j=1}^{\lfloor m/k\rfloor }[d\mid j]=\lfloor \frac{\lfloor m/k\rfloor }{d}\rfloor ,$$

所以，有

$$f(n,m,k)=\sum _d\mu (d)\lfloor \frac{\lfloor n/k\rfloor }{d}\rfloor \lfloor \frac{\lfloor m/k\rfloor }{d}\rfloor .$$

用线性筛预处理完 $\mu (d)$，并预处理其前缀和后，就可以通过数论分块求解．总的时间复杂度为 $O(N+T\sqrt{N})$，其中，$N$ 为 $n,m$ 的上界，$T$ 为数据组数．

题目提供的是最小公倍数，但往往最大公因数更容易处理．所以，首先做变形：

$$f(n)=\sum _{i=1}^n\mathrm{lcm}(i,n)=\sum _{i=1}^n\frac{i\cdot n}{gcd(i,n)}.$$

将 $n$ 提出，并枚举最大公因数 $k$：

$$f(n)=n\sum _{k\mid n}\sum _{i=1}^n\frac{i}{k}[gcd(i,n)=k].$$

对于内层的求和式，这是最常见的含有最大公因数的情形，重复标准的处理流程，就有：

再次地，关于 $i$ 的求和式与其他部分分离，可以单独处理．最后的求和式实际上是一个等差数列求和：（取 $i=d{i}^{\prime }$）

$$\sum _{i=1}^{n/k}i[d\mid i]=d\frac{1}{2}(\frac{n}{kd}+1)\frac{n}{kd}=:dG\left(\frac{n}{kd}\right).$$

由此，就得到如下表达式：

$$f(n)=n\sum _{k\mid n}\sum _d\mu (d)[d\mid \frac{n}{k}]dG\left(\frac{n}{kd}\right).$$

在枚举公因数之后，这样形式的二重求和式很常见．对于它，同样有固定的处理方法：将乘积设为新变量 $\ell =kd$，然后再次交换求和次序．因为 $d\mid (n/k)$ 就相当于 $d\mid \ell \mid n$，所以，原式变形为：

$$f(n)=n\sum _{\ell \mid n}G\left(\frac{n}{\ell }\right)\sum _{d\mid \ell }\mu (d)d.$$

设 $F(\ell )=\sum _{d\mid \ell }\mu (d)d$，则原式具有形式：

$$f(n)=n\sum _{\ell \mid n}G\left(\frac{n}{\ell }\right)F(\ell ).$$

因为 $\mu (d)d$ 是积性函数，所以它和常值函数 $1$ 的卷积 $F(n)$ 也是积性函数．尽管上述表达式中，求和式呈现 Dirichlet 卷积的形式，但是 $G(n)$ 并非积性函数，所以这一求和式的整体并非积性函数．但是，$G(n)$ 是多项式，所以它其实是若干完全积性函数的线性组合．所以，有

$$f(n)=\frac{1}{2}n(\sum _{\ell }{\left(\frac{n}{\ell }\right)}^{2}F(\ell )+\sum _{\ell }\frac{n}{\ell }F(\ell )).$$

这两项（不包含系数）都是积性函数，可以直接通过线性筛预处理（或者也可以线性筛出内层函数后，用 Dirichlet 前缀和在 $O(N\log \log N)$ 时间内预处理）．具体地，设

$$H_s(n)=\sum _{\ell }{\left(\frac{n}{\ell }\right)}^{s}F(\ell ),s=1,2.$$

要推导它们的表达式，只需要确定它们在素数幂处的取值即可．为此，对于素数 $p$ 和正指数 $e$，有

特别地，$H_1(p^e)\equiv 1$ 是常值函数，而

$$H_2(p^e)=p^{2e}+(1-p)\frac{1-p^{2e}}{1-p^2}=H_2(p^{e-1})+p^{2e}-p^{2e-1}.$$

这就很容易通过线性筛求解．在线性筛预处理出 $H_2(n)$ 后，单次询问可以通过表达式 $f(n)=(n/2)(H_2(n)+1)$ 在 $O(1)$ 时间内求解．总的时间复杂度为 $O(N+T)$，其中，$N$ 为 $n$ 的上界，$T$ 为数据组数．

参考实现中，利用本题表达式的特殊性，对线性筛部分做了进一步推导，这并非必须的．仅利用素数幂处的取值，仍然可以在 $O(N)$ 时间内完成预处理．这些推导详见解答二．

就本题而言，有着更为灵活的处理方法．从解答一可以看出

$$f(n)=n\sum _{k\mid n}\sum _{i=1}^{n/k}i[gcd(i,\frac{n}{k})=1]=n\sum _{k\mid n}F\left(\frac{n}{k}\right).$$

如果在这一步不继续做莫比乌斯反演，而是观察后面的求和式实际上是不超过 $d=n/k$ 且与之互素的整数之和．对于 ，因为与 $d$ 互素的整数成对出现，即 $i$ 和 $d-i$ 必定同时与 $d$ 互素，所以，有

$$F(d)=\sum _{i=1}^{n^{\prime }}i[i⟂d]=\sum _{i=1}^d(d-i)[i⟂d]=\frac{1}{2}d\sum _{i=1}^d[i⟂d]=\frac{1}{2}d\phi (d).$$

对于 $d=1$，则有

$$F(d)=1=\frac{1}{2}+\frac{1}{2}d\phi (d).$$

进而，原式可以表示为

$$f(n)=\frac{1}{2}n(\sum _{d\mid n}d\phi (d)+1).$$

由于 $G(n)=\sum _{d\mid n}d\phi (d)$ 是积性函数 $n\phi (n)$ 与常值函数 $1$ 的 Dirichlet 卷积，所以它也是积性函数，可以通过线性筛预处理．为此，只需要确定它在素数幂处的取值．对于素数 $p$ 和正指数 $e$，有

$$G(p^e)=1+\sum _{i=1}^e{p}^e(p^e-1)=G(p^{e-1})+p^{2e}-p^{2e-1}.$$

可以看出，这一表达式和解答一推导的结果是一致的．这一方法的总时间复杂度仍然是 $O(N+T)$．

最后，利用本题积性函数的表达式，可以进一步优化线性筛的计算过程．对于素数 $p$，有

$$G(p)=1-p+p^2.$$

线性筛的关键在于对于一般的 $n$，需要求出 $G(pn)$ 的取值．这进一步分为两种情形．当 $p⟂n$ 时，因为 $G$ 是积性函数，所以

$$G(pn)=G(p)G(n).$$

否则，当 $p\mid n$ 时，设 $n=p^{e}m$ 且 $p⟂m$，就有

直接验证可知，这一表达式对于 $p⟂n$ 的情形也成立．因此，就有

$$G(n)-G\left(\frac{n}{p}\right)=(p^{2e}-p^{2e-1})G(m).$$

代入上式，就得到

$$G(pn)=G(n)+p^2(G(n)-G\left(\frac{n}{p}\right)).$$

这简化了线性筛部分的计算．当然，这一推导并非必需，对于没有特殊性质的积性函数，直接利用 $G(pn)=G(p^{e+1})G(m)$ 就可以完成线性筛的计算．

推导过程中忽略模数．设

$$f(n,m)=\sum _{i=1}^n\sum _{j=1}^m\mathrm{lcm}(i,j).$$

依然是将最小公倍数转换为最大公因数，枚举公因数，并应用标准的处理流程，就得到

再次地，求和式对于 $i$ 和 $j$ 分离．首先计算这些内层的求和式，提取因数（即取 $i=d{i}^{\prime }$），就有

$$\sum _{i=1}^{\lfloor n/k\rfloor }i[d\mid i]=d\sum _{i=1}^{\lfloor \lfloor n/k\rfloor /d\rfloor }i=dG\left(\lfloor \frac{\lfloor n/k\rfloor }{d}\rfloor \right)=dG\left(\lfloor \frac{n}{kd}\rfloor \right).$$

其中，$G(n)={\displaystyle \frac{1}{2}}n(n+1)$ 就是等差数列求和，最后一个等号利用了下取整函数的 特性．对称地，对于另一个和式可以类似计算．代回前文表达式，就有

$$f(n,m)=\sum _{k}k\sum _d\mu (d)d^{2}G\left(\lfloor \frac{n}{kd}\rfloor \right)G\left(\lfloor \frac{m}{kd}\rfloor \right).$$

和前文的情形一致，对于这类枚举公因数的式子，往往都需要枚举乘积 $\ell =kd$，再次交换求和次序：