狄利克雷卷积与莫比乌斯反演
主要内容
- 数论函数
- 狄利克雷卷积
- 积性函数
- 莫比乌斯反演
- 数论分块
提要
\(a \bot b\) 表示 \(a\) 与 \(b\) 互质。
数论函数
数论函数是一类定义域是正整数的函数，可以类比数列。
加法，数乘比较简单，略过。
狄利克雷卷积
定义两个数论函数的狄利克雷卷积为 \(*\)。
若 \(h = f * g\) 则：
\[h(n) = \sum_{i|n} f(i) \cdot g(\frac{n}{i}) \]-
其具有交换律，结合律，分配律等，比较显然。
-
有单位元 \(\epsilon\)，有性质 \(\epsilon * f = f\)。可以得出 \(\epsilon = [n=1]\)。
-
逆元，对于 \(f(1) \not = 0\)，有一个 \(g\) 使得 \(f * g = \epsilon\)。
如何求函数的逆元。
令：
\[g(n) = \frac{1}{f(1)} ([n = 1] - \sum_{i|n,i \not = 1} f(i) \cdot g(\frac{n}{i})) \]可以用方程求出 \(g\)。
如此：
\[f * g = f(1) \cdot g(n) + \sum_{i|n,i\not=1} f(i) \cdot g(\frac{n}{i}) = [n=1] = \epsilon \]积性函数
对于一个数论函数，如果有 \(i \bot j\) 使得 \(f(i \cdot j) = f(i) \cdot f(j)\)。
那么此函数成为积性函数。
如果对于任意的 \(i\)，\(j\) 都有 \(f(i \cdot j) = f(i) \cdot f(j)\) 那么其为完全积性函数。
常见的积性函数有：
-
\(\epsilon\) 解析式 \(\epsilon(n)=[n=1]\)
-
\(id^k\) 解析式 \(id^k(n) = n^k\)
特殊的 \(1(n) = id^0(n) = 1\)
-
\(\phi\) 表示 \([1,n]\) 中与其互质的数的个数。
-
\(\sigma_0\) 表示因数个数。
它们的积性比较显然，不证。
记住两个结论：
-
两个积性函数的狄利克雷卷积是积性函数
-
积性函数的逆是积性函数
比较复杂，不打算证明了。
如何利用积性函数的结论，最简单的是，可以线性筛，因为我们线性筛的过程中顺便求出了其最小的质因子，可以利用积性解决函数的取值。
同时由于积性的性质，函数的取值实际上又其所有质数幂处的取值决定，对于这些取值，\(\phi\) 和 \(\sigma_0\) 都是比较好求的，所以可以用线性筛预处理。
给出质数幂处的公式：
\[\phi(p^k) = (p-1) \cdot p^{k-1} \\ \sigma_0(p^k) = k+1 \]一个重要性质。
尝试证明 \(\phi * 1 =id\)
\[(\phi * 1)(n) = \sum_{i|n} \phi(i) = n \]由于上文提及的狄利克雷卷积的性质，\(\phi * 1\) 为积性函数，\(id\) 也为积性函数，所以只需要证明其在质数幂上相等即可。
显然有：
\[(\phi * 1)(p^k) = \sum_{i=0}^k \phi(p^i) =[ \sum_{i=1}^k (p-1)\cdot p^{i-1}] +1 =( \sum_{i=1}^k p^{i} - p^{i-1} )+1 = p^k = id(p^k) \]得证。
莫比乌斯反演
定义 \(1\) 的逆是 \(\mu\)。
如此，若 \(g = f * 1\)，那么就有 \(f = g * \mu\)。
即若 \(g(n) = \sum_{d|n} f(d)\) 则，\(f(n) \sum_{d|n} \mu(\frac{n}{d})g(d)\)。
比如根据上文性质有 \(\phi = \mu * id\)。
那么有 \(\phi(n) = \sum_{d|n} \mu(\frac{n}{d})d\)。
又有 \(id^k\) 的逆为 \(f(n) = n^k\cdot\mu(n)\)。
我们可以算出
当 \(n=p_1\cdot p_2 \dots p_k\) 其中 \(p\) 为不同的质数时，\(\mu(n)=(-1)^k\)。
否则，\(\mu(n) = 0\)。
记住结论吧。
另一个方向上的莫比乌斯反演。
\(g(x) = \sum_{n|d} f(d)\)
定义新操作 \(\oplus\)。
\((f \oplus g)(x) = \sum_{n|d}f(\frac{d}{n})g(d)\)。
可以证明：
\[(f * g) \oplus h = f \oplus (g \oplus h) \]那么：
\[f = (\mu * 1) \oplus f = \mu \oplus (1 \oplus f) = \mu \oplus g \]所以：
\[f(n) = \sum_{n|d} \mu(\frac{d}{n}) g(d) \]数论分块
浅谈。
经典问题是处理：
\[\sum \lfloor \frac{n}{i} \rfloor f(i) \]我们不难发现 \(\lfloor \frac{n}{i} \rfloor\) 最多有 \(O(\sqrt{n})\) 个取值。
进行一个简单的说明。
当 \(i<\sqrt{n}\) 时：\(i\) 的取值有 \(\sqrt{n}\) 个。
当 \(i>\sqrt{n}\) 时：\(\frac{n}{i}<\sqrt{n}\) 取值有 \(\sqrt{n}\) 个。
考虑如何快速的求出所有 \(\lfloor \frac{n}{i} \rfloor\) 的取值。
for(int i=1,j;i<=n;i=j+1){
j=n/(n/i);
}
证明自行百度，可以感性理解。
此处，既然我们已经求出了 \([i,j]\) 中的数 \(\lfloor \frac{n}{i} \rfloor\) 一致，我们可以把它们放在一起计算，对于 \(f\) 求一个前缀和即可。
对于多元的情况，我们也可以类似的处理。
例题
P1447 [NOI2010] 能量采集
首先定义：
\[f(d) = \sum_{i=1}^n \sum_{j=1}^m [gcd(i,j)=d] \\ \]故有：
\[F(n) = \sum_{n|d} f(d) = \lfloor \frac{n}{d} \rfloor \times \lfloor \frac{m}{d} \rfloor \]答案为：
\[\begin{aligned} ans & = \sum_{i=1}^n \sum_{j=1}^m gcd(i,j) \\ & = \sum_{d=1}^{min(n,m)} f(d) \times d \\ \end{aligned} \]莫比乌斯反演：
\[\begin{aligned} ans & = \sum_{d=1}^{min(n,m)} d \sum_{d|k}^{min(n,m)} \mu(\frac{k}{d}) F(k) \\ & = \sum_{d=1}^{min(n,m)} d \sum_{q=1}^{\frac{min(n,m)}{d}} \mu(q) \times \lfloor \frac{n}{dq} \rfloor \times \lfloor \frac{m}{dq} \rfloor \\ \end{aligned} \]令 \(T = dq\)。
\[\begin{aligned} & = \sum_{d=1}^{min(n,m)} d \sum_{T=1}^{min(n,m)} [d|T] \times \mu(\frac{T}{d}) \times \lfloor \frac{n}{T} \rfloor \times \lfloor \frac{m}{T} \rfloor \\ & = \sum_{d=1}^{min(n,m)} \sum_{d|T}^{min(n,m)} d \times \mu(\frac{T}{d}) \times \lfloor \frac{n}{T} \rfloor \times \lfloor \frac{m}{T} \rfloor \\ \end{aligned} \]更换 \(d\) 和 \(T\) 的枚举顺序。
\[\begin{aligned} & = \sum_{T=1}^{min(n,m)} \sum_{d|T}^{min(n,m)} d \times \mu(\frac{T}{d}) \times \lfloor \frac{n}{T} \rfloor \times \lfloor \frac{m}{T} \rfloor \\ & = \sum_{T=1}^{min(n,m)} \lfloor \frac{n}{T} \rfloor \times \lfloor \frac{m}{T} \rfloor \sum_{d|T}^{min(n,m)} d \times \mu(\frac{T}{d}) \\ \end{aligned} \]关注后面的部分：
\[h(T) = \sum_{d|T} d \times \mu(\frac{T}{d}) \]发现这是狄利克雷卷积的形式。
\[\because h = id * \mu \\ \therefore h * 1 = id * \mu * 1 \\ \therefore h * 1 = id * \epsilon \\ \therefore h * 1 = id \\ \because \phi * 1 =id \\ \therefore h = \phi \]带回原来的式子。
\[ans = \sum_{T=1}^{min(n,m)} \lfloor \frac{n}{T} \rfloor \times \lfloor \frac{m}{T} \rfloor \times \phi(T) \]数论分块即可。
标签：lfloor,frac,狄利克,卷积,sum,rfloor,times,mu,反演 From： https://www.cnblogs.com/DeepSeaSpray/p/18207181