狄利克雷卷积和莫比乌斯反演
狄利克雷卷积
如此定义：
或者可以写为
特殊的函数
- 单位根 \(\varepsilon\)：满足 \(f * \varepsilon = \varepsilon * f = f\)。
- 幂函数 \(Id_k(n) = n^k\)。特殊的，\(Id_1(n) = n\) 为恒等函数，\(Id_0(n) = 1\) 为常函数，简记为 \(I\)。
- 除数函数 \(\sigma_k(n) = \sum_{d|n}^{} {d^k}\)。特殊的，\(\sigma_1(n)\) 为因数和函数，简记为 \(\sigma(n)\)，\(\sigma_0(n)\) 为因数个数函数，简记为 \(\tau(n)\)。
- 欧拉函数 \(\varphi(n)\)。质因数分解 \(n = p_1^{c_1}p_2^{c_2}...p_k^{c_k}\)，则 \(\varphi(n) = n \prod_{i = 1}^k \cfrac {p_i - 1}{p_i}\)。
这些函数都是积性函数，满足 \(gcd(i, j) = 1 \implies f(ij) = f(i)f(j)\)。
函数之间的关系
除数函数和幂函数
根据定义，我们有
即 \(Id_k * I = \sigma_k\)
欧拉函数和恒等函数
根据卷积：
在 \(n = p^k\) 时（\(p\) 为质数），有：
所以 \((\varphi * I)(p^k) = p^k\)
将 \(n\) 质因数分解为 \(\prod p^k\)，根据积性函数的定义，可知：\((\varphi * I)(n) = n = Id_1(n)\)
卷积的逆元
对于一个函数 \(f\)，我们可以如下的定义一个函数 \(g\)。
首先设 \(g(1) = \frac 1 {f(1)}\)。
然后令 \(g(x) = - \frac 1 {f(1)} \sum_{d | x, d > 1}^{} {g(d)f(\frac xd)}\)
于是 \((f * g) = \varepsilon\)
展开带入证明即可。
莫比乌斯函数与莫比乌斯反演
我们定义莫比乌斯函数是 \(I\) 的逆函数，也就是说 \((\mu * I) = \varepsilon\)。
所以，在狄利克雷卷积中：
莫比乌斯函数常用于以下形式
或者可以写作：
而这就是莫比乌斯反演的核心公式。
求法
和欧拉函数 \(\varphi\) 类似，可以通过线性筛的方法在 \(O(n)\) 内求出。
vector<int> prms;
int mob[N], notp[N];
void getMob(int n) {
mob[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!notp[i])
mob[i] = -1, prms.push_back(i);
for (int p : prms) {
int ip = i * p;
if (ip > n) break;
notp[ip] = 1;
if (i % p == 0) {
mob[ip] = 0;
break;
} else mob[ip] = -mob[i];
}
}
}
数论分块（整除分块）
核心问题：求解 \(\sum_{i = 1}^n \lfloor \frac ni \rfloor, n \le 10^{12}\)。
不难得知， \(\lfloor \frac ni \rfloor\) 不同的取值只有 \(O(\sqrt n)\) 个，并且是连续的。所以考虑对于每一中取值，求出有多少个。也就是说，对于 \(i\)，需要求出满足 \(\lfloor \frac ni \rfloor = \lfloor \frac nj \rfloor\) 的最大的 \(j\)。
于是设 \(\lfloor \frac ni \rfloor = k\)
也就是说，对于每一个取值 \(\lfloor \frac ni \rfloor\)，最大在 \(\lfloor \frac n{\lfloor \frac ni \rfloor} \rfloor\) 时满足。
于是可以这样写出代码：
for (int l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
ans += (r - l + 1) * (n / l);
}
莫比乌斯反演的经典结构
结构1
于是对于：
于是最终利用数论分块求即可。复杂度为 \(O(n + \sqrt {\min(n, m)}\)。
但是代码需要注意，每一次取小步跳：
r = min(n / (n / l), m / (m / l));
结构2
于是求 \(\sum_{i = 1}^{n}\sum_{j = 1}^m \gcd(i, j)\) 的方法与结构1类似即可。
结构3
于是求 \(\sum_{x = 1}^n \sum_{y = 1}^m \sigma_0(xy)\) 也就很简单了。
结构4
令 \(P\) 表示质数集合，求：
我们首先提取公因数：
于是根据模型1：
接下来是一个非常经典的套路：枚举 \(T = px\)
于是问题转化为求 \(\sum_{p | T, p \in P} \mu(\frac Tp)\) 的前缀和，这样就可以单次询问 \(O(\sqrt n)\)。
这完全可以通过埃氏筛筛出，复杂度 \(O(n \log \log n)\)，十分优秀。
不过也可以通过线性筛筛出（因为这个函数非积性函数，所以这里不展开）
结构总结
在这类莫比乌斯反演中，经典的两个套路：
提取公因数
枚举 \(T = px\)
其实在 Pecco 的文章中，对于提取公因数这个方法有更加深刻的阐释。其不仅能应用在只有 \(i, j\) 两个变量的模型中，还可以扩展到更多的变量上。
再次膜拜大佬：# 算法学习笔记(36): 莫比乌斯反演
其实一般讲莫比乌斯反演到这里就没有了，但是我看了《离散数学》中的莫比乌斯反演一章。我发现两者根本不在同一个位阶上……这就是颠覆我认知的原因。
所以这里我还要把莫比乌斯反演扩展出来。
莫比乌斯再认识
我们考虑这么一个情况：
有集合 \(X\) 和偏序关系 \((P(X), \subseteq)\)，设：
其中：\(G(S) = \sum_{T \subseteq S}F(T)\)。
则可以求得：\(F(S) = \sum_{T \subseteq S}(-1)^{|S| - |T|}G(T)\)
由 \(G\) 求的 \(F\) 的过程称为反解，其中，\((-1)^{|S|-|T|}\) 就是莫比乌斯函数在这种情况下的取值，也称为容斥系数。
二项式反演
二项式反演可以说是上面内容的一种特殊形式。其满足：
此时我们可以直接通过集合大小表示：\(F(S) = f(|S|), G(S) = g(|S|)\)
于是对于 \(G(K) = \sum_{L \subseteq K} F(L)\)，合并相同大小的子集，即可得到：
根据反演，也就有：
这也就是二项式反演在此的推导，这里的莫比乌斯函数 \(\mu\)，后文再说。
扩展到偏序集
在此，我们扩展到任意有限偏序集 \((X, \le)\)。不过为了得到莫比乌斯函数，我们首先考虑二元变量。
设 \(\mathbb{F}(X)\) 是满足只要 \(x \not \le y\) 就有 \(f(x, y) = 0\) 的所有实数函数的集合。
我们如此定义卷积 \(h = f * g\)：
不难证明卷积满足结合律，这部分留个读者思考。
于是，我们重新定义如下函数：
- 单位函数（克罗内克 delta 函数）：
- 常数函数（zeta function）：
至于莫比乌斯函数，与上文的定义类似，也就是 \(\zeta\) 的逆函数：
于是通过卷积的定义，我们得到：
或等价的：
而等式 \((2.1)\) 意味着，对于所有的 \(x\):
以及：
至于莫比乌斯反演，无非还是：
于是我们重新思考二项式反演，其实就是偏序集 \((P(X_n), \subseteq)\) 上的莫比乌斯反演。
设 \(A\) 和 \(B\) 是 \(X_n\) 的子集，且 \(A \subseteq B\)，有 \(\mu(A, B) = (-1)^{|B| - |A|}\)。
这可以通过归纳假设证明，这里不过多展开。
开篇讲的狄利克雷卷积上的莫比乌斯反演，其实就是偏序集 \((\Z, |)\) 上的莫比乌斯反演。
这东西谁都知道，一元的莫比乌斯函数 \(\mu(x)\) 怎么求。不过我们的目标是计算该偏序集的 \(\mu(a, b)\)。
但是，由于如果 \(a | b\) 则 \(\mu(a, b) = \mu(1, \frac ba)\)。所以我们只需要算 \(\mu(1, x)\) 即可。
而 \(\mu(x)\) 其实就是 \(\mu(1, x)\) ……
考虑离散傅立叶变换。
我们不是有：
我们整理一下重新写出：
根据离散傅立叶逆变换，则有：
其中，\(\frac 1n \omega^{-kx}\) 就是容斥系数，\(\mu(k, x)\)。
最后的最后，提一个题吧：[春季测试 2023] 幂次 - 洛谷。
其实也可以通过容斥（求 \(\mu\)）求解，但并非反演。
参见博客：幂次 - Jijidawang