整除偏序

高维点与整除

记 \(p_k\) 为第 \(k\) 个素数，那么由唯一分解定理，对于任意 \(n\) 有

\[ n=\prod_{i=1}^{+\infty}p_i^{a_i} \]

把每个素数看作是一个维度，那么每个数 \(n\) 就是一个高维空间中的点。

对 \(n,m\)，分别记他们的唯一分解式为

\[ \begin{aligned} n&=\prod_{i=1}^{+\infty}p_i^{a_i}\\ m&=\prod_{i=1}^{+\infty}p_i^{b_i} \end{aligned} \]

\(\gcd(n,m)\) 和 \(\operatorname{lcm}(n,m)\) 分别为：

\[ \begin{aligned} \gcd(n,m)&=\prod_{i=1}^{+\infty}p_i^{\min(a_i,b_i)}\\ \operatorname{lcm}(n,m)&=\prod_{i=1}^{+\infty}p_i^{\max(a_i,b_i)} \end{aligned} \]

下面所有讨论提及 \(n,m\) 时都假设 \(m\mid n\)。

定义函数 \(f\) 的 zeta 变换 \(f\zeta\)

\[ f\zeta(n)=(f*\mathbf{I})(n)=\sum_{d\mid n}f(d) \]

我们知道，若 \(m\mid n\) 则有 \(\forall i, b_i\le a_i\)，不难注意到整除是构成一个偏序关系的，我们称这为整除偏序，zeta 变换实际上是在整除偏序上做了一个高维前缀和。

既然有高维前缀和，当然也要有高维差分。我们当然知道这是卷上 \(\mu\)，但下面让我们从组合意义的视角看看 \(\mu\) 是怎么来的。

设 \(g=f\zeta\)， 给定 \(g\)，考虑怎么对每个 \(n\) 还原出 \(f(n)\)。

先减去所有 \(m\) 比 \(n\) 在一个素数处指数比 \(n\) 小 \(1\) 的 \(g(m)\)，那如果 \(m\) 比 \(n\) 在两个素数处指数比 \(n\) 小 \(1\) 就减多了，再加回这部分的 \(g(m)\)，再减去三个素数处指数比 \(n\) 小 \(1\) 的……

这个小 \(1\) 只是在钦定某几维比 \(n\) 小，也就是减的时候会把所有这几维比 \(n\) 小的全部减掉，所以不会漏算。

显然，\(m\) 的容斥系数为：

\[ \left[\frac{n}{m}没有平方因子\right](-1)^{\frac{n}{m}的素因子个数} \]

也就是。

\[ f(n)=(g*\mu)(n) \]

那么我们定义 \(f\) 的 Möbius 变换 \(f\mu\) 是

\[ f\mu=\sum_{d\mid n}f(d)\mu\left(\frac{n}{d}\right) \]

更快速的狄利克雷卷积

不妨假设 \(f\) 是任意数论函数，而 \(g\) 是任意积性函数。现在我们要求

\[ (f*g)(n) \]

的前 \(n\) 项。直接根据定义做就可以达到

\[ \sum_{i=1}^{n}\sigma_0(i)=\mathcal O(n\log n) \]

的复杂度，且不要求 \(g\) 的积性。但是当我们在 \(g\) 是某一个积性函数的时候会不会有更好的做法？

zeta 变换

先来看几个简单的情况，比如我们怎么快速计算

\[ f\zeta(n)=\sum_{d\mid n}f(d) \]

的前 \(n\) 项。

引理

设 \(g_k(k^t)=1\)，其余位置为 \(0\)，那么 \(g\) 是积性函数，且设

\[ f=g_{p_1}*g_{p_2}*g_{p_3}*\cdots *g_{p_{\pi(n)}} \]

那么对所有 \(i\le n\)，有 \(f(i)=1\)。

证明： 考虑归纳法。

假设对于 \(i-1\)，所有质因子集合为 \(\{p_1,p_2,\cdots, p_{i-1}\}\) 子集的数 \(n\)，均有 \(f(n)=1\)，否则 \(f(n)=0\)。

那么考察 \(f*g(n)\)

\[ (f*g)(n)=\sum_{d\mid n}f\left(\frac{n}{d}\right)g\left(d\right) \]

记 \(t=p_i^{v_{p_i}(n)}\)，那么显然当且仅当 \(d=t\) 的时候 \(f\left(\frac{n}{d}\right)=1,g\left( d\right)=1\)，否则两者必有一为 \(0\)。

从而有对于 \(i\)，所有质因子集合为 \(\{p_1,p-2,\cdots, p_{i}\}\) 子集的数 \(n\) 均有 \(f(n)=1\)，否则 \(f(n)=0\)。

因为我们只要前 \(n\) 项，那现在就是计算

\[ f*g_{p_1}*g_{p_2}*\cdots *g_{p_{\pi(n)}} \]

考虑从小到大枚举素数，当前素数为 \(p\)，已知 \(f\)，要求 \(f*g_p\)。

\[ f*g_p(n)=\sum_{p^k\mid n}f\left(\frac{n}{p^k}\right) \]

注意到一个性质是，所有 \(t\ge 1\)，有 \(\frac{n}{p^t}\mid \frac{n}{p}\)，所以就有：

\[ \begin{aligned} f*g_p\left(\frac{n}{p}\right)&=\sum_{p^k\mid \frac{n}{p}}f\left(\frac{n}{p^k}\right)\\ f*g_p\left(n\right)&=f*g_p\left(\frac{n}{p}\right)+f(n) \end{aligned} \]

所以如果对所有 \(m<n\) 的 \(f(n)\) 都已经维护出了正确的值，转移直接

\[ f(n)\leftarrow f(n)+f\left(\frac{n}{p}\right) \]

Möbius 变换