狄利克雷卷积 & 莫比乌斯反演

定义两个数论函数 \(f(x),g(x)\) 的狄利克雷卷积 \((f*g)(x)\) 为

\[ (f*g)(x)=\sum_{i|x}f(i)g(\frac xi) \]

性质 1：狄利克雷卷积具有交换律，结合律；
性质 2：其单位元 \(\epsilon(x)\) 为 \(\epsilon(x)=[x=1]\)；
性质 3：两个积性函数的狄利克雷卷积还是积性函数；
性质 4：若一个数论函数 \(f\) 满足 \(f(1)\ne 0\)，那么其存在逆元；

现在介绍几个重要的数论函数：

\(\operatorname I(x)=1\)：常函数；
\(\operatorname{Id}(x)=x\)：线性函数（我瞎叫的）；
\(\operatorname{Id}^k(x)=x^k\)：幂函数；
\(\varphi(x)\)：不用多说了吧；
\(\mu(x)\)：莫比乌斯函数；
\(d(x)\)：因数个数函数；
\(\sigma^k(x)\)：因数（\(k\) 次方和）和函数；

这里说一下莫比乌斯函数，对于正整数 \(n=\prod{p_i^{\alpha_i}}\)（质因数分解），\(\mu(x)\) 定义为：

\[ \mu(x)= \begin{cases} 0,&\exist\alpha_i\ge 2\\ (-1)^{\sum[\alpha_i=1]},&\forall\alpha_i\in\{0,1\} \end{cases} \]

不难证明 \(\mu(x)\) 是积性函数，因此可以使用线性筛。

推论 1：\(\mu*\operatorname{I}=\epsilon\)（莫比乌斯反演）；
推论 2：\(\varphi*\operatorname{I}=\operatorname{Id}\)（欧拉反演）；
推论 3：\(\operatorname{Id}^k*\operatorname{I}=\sigma^k\)（废话）；

证明：

（推论 1）由于 \(\mu*\operatorname{I}\) 还是积性函数，因此只需证明 \((\mu*\operatorname{I})(p^k)=[k=0]\)：

\[ \sum_{i|p^k}\mu(i)=\sum_{i=0}^{k}\mu(p^i)= \begin{cases} 1+(-1)+0+0+\cdots,&(k\ge 1)\\ 1,&(k=0) \end{cases} \]

（推论 2）考虑拆贡献，把 \(1\sim n\) 的每一个数字 \(x\) 放到 \(\gcd(x,n)\) 处统计：

\[ \sum_{i=1}^{n}1=\sum_{i|n}\sum_{i|j\wedge j\le n}[\frac ji\bot\frac ni]=\sum_{i|n}\varphi(\frac ni) \]

将数字 \(n\) 质因数分解为 \(\prod p_i^{\alpha_i}\)，然后就可以写成一个无穷维向量 \((\alpha_1,\alpha_2,\alpha_3,\alpha_4,\cdots)\) 分别表示每个质因子的次数。那么数论函数就是一个向量到数值的映射，卷 \(\operatorname{I}\) 对应着高维前缀和，卷 \(\mu\) 对应高维差分。

狄利克雷前缀和 & 差分

给定数论函数 \(f(x)\)，如何快速计算 \(f*\operatorname{I}\) 和 \(f*\mu\) 呢？暴力卷积显然是 \(O(n\ln n)\) 的。注意到高维前缀和可以逐维度考虑，依次进行前缀和。因此枚举质数 \(p\)，然后执行 \(f(i)\to f(pi)\)（箭头表示贡献）。这样只有 \(\lfloor\frac np\rfloor\) 个 \(i\) 会被处理，因此时间复杂度同埃氏筛，为 \(O(n\ln\ln n)\)。

P2522 [HAOI2011] Problem b

给定 \(n,m\)，求

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

\(n,m\le 5\times 10^4\)，多组询问，询问次数 \(\le 5\times 10^4\)

考虑到 \([x=1]=\sum\limits_{i|x}\mu(i)\)，因此上式可以写成

\[ \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|\gcd(i,j)}\mu(d)=\sum_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor \]

筛出 \(\mu(x)\) 后整除分块即可。