零，前言
主要内容及顺序：积性函数 → 几种常见积性函数 → 狄利克雷卷积 → 莫比乌斯反演 → 狄利克雷前缀和
所有性质/结论都有证明，请放心食用。
本文中，变量 \(p\) 的取值范围是质数集。
一，基础知识
定义域为 \(\bf N^*\) 的函数称为数论函数。
若数论函数 \(f\) 满足：\(f(mn)=f(m)f(n)\) 对所有互质的 \(m,n\) 都成立，则 \(f\) 是积性函数。
若 \(f(mn)=f(m)f(n)\) 对任意 \(m,n\) 都成立，则 \(f\) 是完全积性函数。
如果积性函数 \(f\) 不恒为 \(0\) ，那么 \(f(1)=1\) 一定成立。
本文将会讨论到如下函数：
| 函数名 | 定义式 | 介绍 | 性质 |
|---|---|---|---|
| 素因子个数 \(\omega\) | \(\omega(n)=\sum\limits_{p\vert n}1\) | \(n\) 的素因子个数 | 对互质的 \(m,n\) 有 \(\omega(mn)=\omega(m)+\omega(n)\) |
| 因子个数 \(\tau\) | \(\tau(n)=\sum\limits_{d\vert n}1\) | \(n\) 的因子个数，有时也写作 \(d,\sigma_0\) | 积性 |
| 因子和 \(\sigma\) | \(\sigma(n)=\sum\limits_{d\vert n}d\) | \(n\) 的因子之和，有时也写作 \(\sigma_1\) | 积性 |
| 欧拉函数 \(\varphi\) | \(\varphi(n)=\sum\limits_{d=1}^n[d\perp n]\) | \(1\sim n\) 中与 \(n\) 互质的数的个数 | 积性 |
| 莫比乌斯函数 \(\mu\) | \(\mu(n)=\begin{cases}0,&\exists d\in{\bf N^*},d^2\vert n\\(-1)^{\omega(n)},&\rm otherwise.\end{cases}\) | 初学者可能觉得比较奇怪，但先记住就好 | 积性 |
| 元函数 \(\varepsilon\) | \(\varepsilon(n)=[n=1]\) | 狄利克雷卷积的单位元 | 完全积性 |
| 常函数 \(I\) | \(I(n)=1\) | 常见于狄利克雷卷积 | 完全积性 |
| 单位函数 \(\rm id\) | \({\rm id}(n)=n\) | 常见于狄利克雷卷积 | 完全积性 |
注：\([P]\) 为艾弗森括号，当命题 \(P\) 为真时取值为 \(1\) ，否则取值为 \(0.\)
关于上述函数积性的证明：
-
\(\tau,\sigma\)
设 \(m,n\) 互质，则对于 \(mn\) 的因子 \(T\)，一定存在 \(m\) 的因子 \(d\) 和 \(n\) 的因子 \(t\) 满足 \(T=dt\)，并且 \(T\) 和 \((d,t)\) 是一一对应的。
那么当 \(T\) 对 \(\tau(mn)\) 产生贡献时，\(d,t\) 也会对 \(\tau(m)\tau(n)\) 产生相等的贡献。
于是 \(\tau(mn)=\tau(m)\tau(n)\)，即 \(\tau\) 具有积性。\(\sigma\) 同理。
关键在于互质导致了两部分贡献独立。后面还会用到这个。
-
\(\varphi\)
其实不太好证。我们暂且不提，先讲狄利克雷卷积，然后再证就很容易了。（放心，没有循环论证）
-
\(\mu\)
直接用定义证明。设 \(m,n\) 互质，只需证 \(\mu(mn)=\mu(m)\mu(n).\)
若 \(m\) 或 \(n\) 有平方因子，那么 \(mn\) 也有平方因子，于是 \(\mu(mn)=0=\mu(m)\mu(n)\)；
若 \(m,n\) 都没有平方因子，又因为 \(m,n\) 互质，那么 \(mn\) 也没有平方因子。则 \(\mu(mn)=(-1)^{\omega(mn)}=(-1)^{\omega(m)+\omega(n)}=\mu(m)\mu(n).\)
-
\(\varepsilon,I,{\rm id}\)
这有啥好证的。
要确定一个积性函数，只需知道它在质数幂 \(p^k\) 处的定义（这一般是很简单的）。然后利用积性即可推出完整定义。
以 \(\tau,\sigma,\varphi\) 为例，我们容易证明：
\[\begin{aligned} \tau(p^k) &= k+1 \\ \sigma(p^k) &= 1+p+p^2+\cdots+p^k \\ \varphi(p^k) &= p^k-p^{k-1} = p^k\left(1-\frac1p\right) \end{aligned}\]进而可以得到 \(\tau,\sigma,\varphi\) 的计算式：
设 \(n\) 的素因子分解式为 \(n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}\)，那么
\[\begin{aligned} \omega(n) &= k \\ \tau(n) &= \prod_{i=1}^k(\alpha_i+1) \\ \sigma(n) &= \prod_{i=1}^k(1+p_i+p_i^2+\cdots+p_i^{\alpha_i}) \\ \varphi(n) &= n\prod_{i=1}^k\left(1-\dfrac1{p_i}\right) \end{aligned}\]二，狄利克雷卷积
定义数论函数 \(f,g\) 的狄利克雷卷积（数论卷积）为：
\[(f*g)(n)=\sum_{d|n}f(d)g\Big(\frac nd\Big) \]狄利克雷卷积的一些性质：
-
单位元为 \(\varepsilon\) ：对任意 \(f\) 都有 \(f*\varepsilon=f.\)
-
满足交换律：\(f*g=g*f.\)
-
满足分配律：\((f+g)*h=(f*h)+(g*h).\)
这里的加法就是直接把对应函数值相加，即 \((f+g)(n)=f(n)+g(n).\) -
满足结合律：\((f*g)*h=f*(g*h).\)
-
若 \(f,g\) 都是积性函数，则 \(f*g\) 也是积性函数。
-
\(\mu*I=\varepsilon.\) 即 \(\mu\) 与 \(I\) 互为逆元。
-
\(\varphi*I={\rm id}.\)
1,2,3：显然的，不再证明。
4：不太显然，稍微证一下。
已知 \(f,g,h\) 为数论函数，求证：\((f*g)*h=f*(g*h).\)
记 \(F=(f*g)*h\)，直接考虑 \(F(n)\) 的贡献来自哪些项。
容易发现：\(f(i)g(j)h(k)\) 对 \(F(n)\) 有贡献，当且仅当 \(ijk=n.\)
也就是 \(F(n)=\sum\limits_{ijk=n}f(i)g(j)h(k).\) 同理 \(f*(g*h)\) 也有相同的式子。
因此 \((f*g)*h=f*(g*h).\)
5：也不太显然。但可以参考前文对 \(\tau,\sigma\) 积性的证明，基本上是同理的。这里就不再详细写了。
6,7：为了证明它们，这里补充一个不知道名字但是很牛逼的证明技巧：
对于积性函数 \(f,g\) ，要证明 \(f=g\)，只需证 \(f(p^k)=g(p^k)\) 恒成立。
正确性：如果你有好好看前面的内容的话，应该是显然的。（
求证：\(\sum\limits_{d|n}\mu(d)=[n=1]\) ，即 \(\mu*I=\varepsilon.\)
显然两边都是积性函数，符合上述技巧的适用前提。
\[(\mu*I)(p^k)=\sum_{d|p^k}\mu(d)=1+(-1)+0+0+\cdots=0=\varepsilon(p^k) \]至此可知 \(\mu*I=\varepsilon.\)
求证：\(\sum\limits_{d|n}\varphi(d)=n\)，即 \(\varphi*I={\rm id}.\)
同样可以使用上述技巧。
\[(\varphi*I)(p^k)=\sum_{d|p^k}\varphi(d)=1+(p-1)+(p^2-p)+\cdots+(p^k-p^{k-1})=p^k={\rm id}(p^k) \]但是这个结论还有另外一个同样简洁优美的证法，值得一看：
将 \(i=1,2,\cdots,n\) 按照 \(\gcd(i,n)\) 归类，\(i\) 的总个数不变，仍然为 \(n\) ：
\[\sum_{d|n}\sum_{i=1}^n[\gcd(i,n)=d]=n \]上式等价于
\[\sum_{d|n}\sum_{i=1}^{n/d}[\gcd(i,\tfrac nd)=1]=n \]而 \(\sum\limits_{i=1}^{n/d}[\gcd(i,\frac nd)=1]\) 就是 \(\varphi(\frac nd)\) ！
\[\sum_{d|n}\varphi\Big(\frac nd\Big)=n \]也就是
\[\sum_{d|n}\varphi(d)=n \]证毕。
三，莫比乌斯反演
莫比乌斯反演的公式：
\[f(n)=\sum_{d|n}g(d)\qquad\Longleftrightarrow\qquad g(n)=\sum_{d|n}\mu\Big(\frac nd\Big)f(d) \]试着用狄利克雷卷积重写一下：
\[f=g*I\qquad\Longleftrightarrow\qquad g=f*\mu \]由 \(\mu*I=\varepsilon\) 可知该式显然正确。
还有个反方向的形式：
\[f(n)=\sum_{n|d}g(d)\qquad\Longleftrightarrow\qquad g(n)=\sum_{n|d}\mu\Big(\frac dn\Big)f(d) \]证明略。
填一下前文留的坑：证明 \(\varphi\) 的积性。
由 \(\varphi*I={\rm id}\) 可知 \(\varphi=\mu*{\rm id}\)，而 \(\mu\) 和 \(\rm id\) 都是积性函数，所以 \(\varphi\) 也是积性函数。
下面给出一道例题，展示一下莫比乌斯反演在 OI 题中的用法。
\(T\) 组数据，每次给定 \(a,b,d\)，求 \(\sum\limits_{i=1}^a\sum\limits_{j=1}^b[\gcd(i,j)=d].\)
\(1\le T\le 50000,~1\le d\le a,b\le 50000.\)
设 \(f(n)\) 表示最大公约数为 \(n\) 的二元组 \((i,j)\) 个数，
设 \(g(n)\) 表示公约数为 \(n\) 的二元组 \((i,j)\) 个数。
注意到 \(g(n)=\sum\limits_{n|d}f(d)\) 且 \(g(n)=(a/n)(b/n).\)
应用莫比乌斯反演：\(f(n)=\sum\limits_{n|d}\mu(\frac dn)g(d).\)
然后就容易得到答案为 \(\sum\limits_{t=1}^{\infty}\mu(t)(a/dt)(b/dt).\)
可以认为 \(t\) 有上界 \(\min(a,b)/d\)，因为 \(t>\min(a,b)/d\) 时后面的项都是 \(0.\)
线性筛求 \(\mu\)，然后整除分块计算答案。
时间复杂度 \(O(n+T\sqrt n)\)，其中 \(n=50000.\)
虽然思路很简洁，但设函数、找关系的过程还是要思考一下。有没有无脑做法呢？
其实是有的。我们不使用莫比乌斯反演，而是用这个式子做代换：\([\gcd(i,j)=1]=\sum\limits_{d|i,d|j}\mu(d).\)
下面是推式子的过程：
\[\begin{aligned} \sum_{i=1}^a\sum_{j=1}^b[\gcd(i,j)=d] &= \sum_{i=1}^{a/d}\sum_{j=1}^{b/d}[\gcd(i,j)=1]\\ &= \sum_{i=1}^{a/d}\sum_{j=1}^{b/d}\sum_{t|i,t|j}\mu(t)\\ &= \sum_{t=1}^{a/d}\mu(t)\left\lfloor\dfrac {a/d}t\right\rfloor\left\lfloor\dfrac {b/d}t\right\rfloor \end{aligned}\]代换之后只需要无脑换序求和就行了。
实际做题时常用这种方法代替莫比乌斯反演。
四，闲话 & 狄利克雷前缀和
关于莫反本质的一些理解：
整除是一种偏序关系。
莫比乌斯反演实际上是偏序集上的一种容斥。莫比乌斯函数 \(\mu\) 即为容斥系数。
本文中讨论的是数论版本的莫比乌斯反演。这种情形的特殊之处在于 \(\mu\) 很好计算，所以在 OI 中应用较广。
顺便提一下狄利克雷前缀和。
给定 \(a_1\sim a_n\)，求 \(b_1\sim b_n\)，满足 \(b_k=\sum\limits_{i|k}a_i.\)
答案对 \(P=2^{32}\) 取模。
使用随机数生成器进行读入。只需输出 \(b_1\sim b_n\) 的异或和。总之不用担心 IO 问题。\(1\le n\le 2\times10^7.\)
枚举倍数计算的时间复杂度是 \(O(n\ln n)\)，显然寄了。
观察 \(b_k\) 的定义式：对所有满足 \(i|k\) 的 \(a_i\) 求和。
记 \(\nu_p(n)\) 表示 \(n\) 包含因子 \(p\) 的个数。
那么 \(i|k\) 就等价于，对任意质数 \(p\)，都有 \(\nu_p(i)\le \nu_p(k).\)
将每个 \(p\) 都作为一个维度来看，我们发现 \(b\) 就是 \(a\) 的高维前缀和！
计算高维前缀和，只需在每个维度上都做一次前缀和即可。
代码实现：
for (int i=2; i<=n; ++i) if (!v[i]) //和埃筛同时进行
for (int j=i,k=1; j<=n; j+=i,++k)
v[j]=1,a[j]+=a[k]; //做前缀和
时间复杂度与埃筛相同，是 \(O(n\log\log n)\)，可以通过。
标签：函数,limits,狄利克,卷积,sum,varphi,mu,反演,积性 From： https://www.cnblogs.com/icyM3tra/p/17103105.html