初等数论学习笔记 III：数论函数与筛法( 四 ) _生活百科

对每个 \(n\) 计算给定数论函数在其所有因数处的取值之和有很好的实际含义，因此狄利克雷前缀和是比较重要的算法。
将每个数 \(n\) 写成无穷序列 \(a_n = \{c_1, c_2, \cdots, c_i, \cdots\}\) 表示 \(n = \prod p_i ^ {c_i}\) ，其中 \(p_i\) 表示第 \(i\) 个质数。因为 \(x\mid y\) 的充要条件为 \(a_x(c_i) \leq a_y(c_i)\)，所以 \(f * 1\) 可以看成对下标做关于其无穷序列的高维前缀和，即 \(g(n) = \sum\limits_{\forall i, a_d(c_i) \leq a_n(c_i)} f(d)\) 。
根据高维前缀和的求法，枚举每一维并将所有下标关于该维做前缀和，可得狄利克雷前缀和的实现方法：初始令 \(x_i = f(i)\) 。从小到大枚举每个质数 \(p_i\)，枚举 \(k\)，将 \(x_{p_ik}\) 加上 \(x_k\)，相当于 \(k\) 贡献到给 \(a_k(i)\) 加上 \(1\) 之后的下标。最终得到的 \(x\) 即为 \(g\) 。
根据小于 \(n\) 的素数倒数之和为 \(\ln\ln n\) 这一结论，狄利克雷前缀和的时间复杂度为 \(\mathcal{O}(n\ln\ln n)\) 。
模板题 P5495 代码。
#include <bits/stdc++.h>using namespace std;constexpr int N = 2e7 + 5;int n;unsigned ans, a[N], seed;inline unsigned rd() {seed ^= seed << 13, seed ^= seed >> 17, seed ^= seed << 5;return seed;}bool vis[N];int cnt, pr[N >> 3];void sieve() {for(int i = 2; i <= n; i++) {if(!vis[i]) pr[++cnt] = i;for(int j = 1; j <= cnt && i * pr[j] <= n; j++) {vis[i * pr[j]] = 1;if(i % pr[j] == 0) break;}}}int main() {cin >> n >> seed, sieve();for(int i = 1; i <= n; i++) a[i] = rd();for(int i = 1; i <= cnt; i++)for(int j = 1; j * pr[i] <= n; j++)a[j * pr[i]] += a[j];for(int i = 1; i <= n; i++) ans ^= a[i];cout << ans << endl;return 0;}4. 数论分块数论分块又称整除分块，因其解决的问题与整除密切相关而得名。数论分块用于求解形如
\[\sum_{i = 1} ^ n f(i) g\left(\left\lfloor\dfrac n i \right\rfloor\right)\]的和式。前提为 \(f\) 的前缀和可快速计算。
感性认知：使得 \(\left\lfloor\dfrac n x\right\rfloor = k\) 的正整数 \(x\) 的范围为 \(\left(\left\lfloor \dfrac n {k + 1}\right\rfloor, \left\lfloor \dfrac n k\right\rfloor \right]\) 。
4.1 算法介绍如果 \(\left\lfloor\dfrac n i\right\rfloor\) 的数量不多，可以考虑转换贡献形式，将原式写成若干 \(g\left(\left\lfloor\dfrac n i\right\rfloor\right)\) 乘以一段 \(f\) 的和。接下来分析不同 \(\left\lfloor\dfrac n i\right\rfloor\) 的数量的上界。
当 \(i\) 较大时，\(\left\lfloor \dfrac {n} {i} \right\rfloor\) 被限制在较小范围内，很多 \(\left\lfloor \dfrac {n} {i}\right\rfloor\) 均相同。结合 \(\min\left(i, \dfrac n i\right) \le \sqrt n\)，可以想到根号分治。

结论 1：对于任意 \(i\in [1, n], n\in \mathbb N_+\)，不同的 \(\left\lfloor \dfrac {n} {i}\right\rfloor\) 至多 \(2\sqrt n\) 个。

证明：\(i \leq \sqrt n\) 时，\(\left\lfloor \dfrac {n} {i}\right\rfloor\) 只有 \(\sqrt n\) 个；\(i > \sqrt n\) 时， \(\left\lfloor \dfrac {n} {i}\right\rfloor \leq \sqrt n\)，只有 \(\sqrt n\) 个。证毕。
根据结论 1，枚举 \(\mathcal{O}(\sqrt n)\) 种整除值 \(d\)，求出最小和最大的 \(i\) 使得 \(\left\lfloor\dfrac n i\right\rfloor = d\)，分别记作 \(l, r\) ，则原式可写为 \(\sum\limits_{d} g(d)\sum\limits_{i = l} ^ r f(i)\) 。因此，只要 \(f\) 的前缀和可以快速计算，\(g\) 在某处的取值可以快速得到，即可在 \(\mathcal{O}(\sqrt n)\) 的时间内解决原问题。
这样，问题转化为求使得 \(\left\lfloor\dfrac n i\right\rfloor = d\) 的最小和最大的 \(i\) 。
\(\left\lfloor\dfrac n i\right\rfloor = d\) 对 \(i\) 有两条限制，分别为 \(i(d + 1) > n\) 和 \(id \leq n\) 。因为使得 \(id\leq n\) 的最大的 \(i\) 就是 \(\left\lfloor\dfrac n d\right\rfloor\)，同理使得 \(i(d + 1) \leq n\) 的最大的 \(i\) 为 \(\left\lfloor\dfrac n {d + 1}\right\rfloor\) ，所以 \(l = \left\lfloor\dfrac n {d + 1}\right\rfloor + 1\)，\(r = \left\lfloor\dfrac n d\right\rfloor\) 。
如何不重不漏地枚举所有整除值？没有必要。我们只需依次枚举每个 \(i\)，并借助上述工具跳过 \(\left\lfloor\dfrac n i\right\rfloor\) 相同的极长连续段即可。
具体地，令当前枚举到的 \(i\) 为 \(l\)，此时整除值为 \(d = \left\lfloor\dfrac n i\right\rfloor\) 。因为使得 \(\left\lfloor\dfrac n i\right\rfloor = d\) 的最大的 \(i\) 等于 \(\left\lfloor\dfrac n d\right\rfloor\) ，所以令 \(r = \left\lfloor\dfrac n {\left\lfloor\frac n l\right\rfloor}\right\rfloor\)，将 \(g(d)(s(r) - s(l - 1))\) 累和入答案，并令 \(l \gets r + 1\) 表示跳过 \(l + 1\sim r\) 这一段 \(i\)，若 \(l > n\) 则退出。其中 \(s\) 是 \(f\) 的前缀和。