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

根据高维前缀和的求法，枚举每一维并将所有下标关于该维做前缀和，可得狄利克雷前缀和的实现方法：初始令 \(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\) 相同的极长连续段即可。