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

vector 存储所有 \(f_i\) 并转移，时间复杂度 \(\mathcal{O}(n\sqrt {a_i})\) 。滚动数组优化后空间复杂度 \(\mathcal{O}(n)\) 。代码。
III. P2260 [清华集训2012] 模积和求 \(\sum\limits_{i = 1} ^ n n \bmod i\) 是经典问题：拆成 \(\sum\limits_{i = 1} ^ n \left(n - \left\lfloor\dfrac n i\right\rfloor i\right)\) 后数论分块，时间复杂度 \(\mathcal{O}(\sqrt n)\) 。
原式可写作
\[\left(\sum_{i = 1} ^ n n\bmod i\right) \left(\sum_{i = 1} ^ m m\bmod i\right) - \sum_{i = 1} ^ {\min(n, m)} \left(n - \left\lfloor\dfrac n i \right\rfloor i\right)\left(m - \left\lfloor\dfrac m i\right\rfloor i \right)\]全部使用数论分块解决。可能需要的公式：\(\sum\limits_{i = 1} ^ ni ^ 2 = \dfrac{n(n + 1)(2n + 1)} 6\) 。
时间复杂度 \(\mathcal{O}(\sqrt n)\)，代码。
*IV. P3579 [POI2014] PAN-Solar Panels非常不错的题目。
当 \(\lfloor\frac {a - 1} k\rfloor < \lfloor\frac b k\rfloor\) 且 \(\lfloor\frac{c - 1} k\rfloor < \lfloor\frac d k\rfloor\) 时，\([a, b]\) 和 \([c, d]\) 均含有 \(k\) 的倍数。答案为所有这样的 \(k\) 的最大值。
我们当然可以四维数论分块，但注意到在使得 \(\lfloor\frac b k \rfloor\) 相同且 \(\lfloor \frac d k\rfloor\) 相同的 \(k\) 的区间 \([l, r]\) 当中，选择 \(k = r\) 可以使 \(\lfloor \frac{a - 1} k\rfloor\) 和 \(\lfloor \frac {c - 1} k\rfloor\) 尽可能?。谢崧阋?。也就是说，若 \(k = r\) 都不满足条件，则 \(l\leq k \leq r\) 均不满足条件。因此二维数论分块即可。
时间复杂度 \(\mathcal{O}(T\sqrt V)\)，代码。
5. 莫比乌斯函数前置知识：容斥原理。
到达数论最高城，莫比乌斯反演！太好用啦莫反，哎呀这不 GCD 么，还是枚举倍数吧家人们。
5.1 引入观察 \(\mu(n)\) 的定义式 \(\begin{cases} 1 & n = 1 \\ 0 & \exists d > 1, d ^ 2\mid n \\ (-1) ^ {\omega(n)} & \mathrm{otherwise} \end{cases}\)，读者也许会好奇数学家为什么要定义如此奇怪的函数。这背后必然隐藏着其某种神秘而重要的性质。
\(g(n) = \sum\limits_{d\mid n} f(d)\) 的狄利克雷前缀和形式相当常见，因此根据 \(g\) 求原函数 \(f\) 也很重要。因为 \(g = f * 1\)，所以 \(f = g * 1 ^ {-1}\) 。
设 \(h = 1 ^ {-1}\)，根据逆元递推式推导 \(h\) 的一般形式。先将递推式写出，\(h(n) = -\sum\limits_{d\mid n, d\neq n} h(d)\) 。
由于积性函数的逆元具有积性，所以 \(h\) 具有积性。只需观察 \(h\) 在质数幂 \(p ^ k\) 处的取值即可得到一般化的结论。

\(h(p) = -h(1) = -1\) 。
\(h(p ^ 2) = -(h(1) + h(p)) = 0\) 。
\(h(p ^ 3) = -(h(1) + h(p) + h(p ^ 2)) = 0\) 。

据此，可归纳证明 \(h(p ^ k)\) 当 \(k = 0\) 时等于 \(1\) ， \(k = 1\) 时等于 \(-1\)，\(k \geq 2\) 时等于 \(0\) 。
考虑 \(n = \prod\limits_{i = 1} ^ m p_i ^ {c_i}\) 。根据 \(h\) 的积性，若存在 \(c_i\geq 2\) 则 \(h(n) = 0\)，否则 \(h(n)\) 等于 \((-1) ^ m\) 。容易发现这与莫比乌斯函数的定义式相符。因此 \(1 ^ {-1} = \mu\)，即
\[\mu * 1 = \epsilon\]验证：令 \(S(n) = \sum\limits_{d\mid n} \mu(d)\) 。考虑 \(n\) 的所有质因子 \(p_1 \sim p_m\) 。对于任意 \(k\) 个质因子的乘积 \(P\)，它产生 \(\mu(P) = (-1) ^ k\) 的贡献。因此，\(S(n)\) 可写作 \(\sum\limits_{i = 0} ^ m (-1) ^ i\dbinom m i = (1 - 1) ^ m\) 。当 \(m = 0\) 时，\(n = 1\)，\(S(n)\) 显然为 \(1\) 。否则 \(S(n) = 0 ^ m = 0\) 。这从另一个角度说明了 \(\mu * 1 = \epsilon\) 。
也可以从容斥系数的角度理解莫比乌斯函数。设 \(g(n) = \sum\limits_{n\mid d} f(d)\)，即 \(g(n)\) 是 \(f\) 在所有 \(n\) 的倍数处的取值和。现在已知 \(g\) ，要求 \(f(1)\) 。则 \(f(1)\) 等于 \(f\) 在 \(1\) 的倍数处的取值和，减去在质数处的取值和，但是多减去了在两个不同质数乘积处的取值和，因此要加上这些值，但是多加上了在三个不同质数乘积处的取值和，以此类推。因此，若 \(n\) 为 \(k\) 个不同质数的乘积，则 \(f(1)\) 会受到 \(g(n)\) 系数为 \((-1) ^ k\) 的贡献，如下图，图源。

文章插图
换言之，对 \(\pmb {\mathbb N}\) 做容斥原理，得到贡献系数 \(\boldsymbol \mu\) 。
5.2 筛据定义，线性筛莫比乌斯反演是容易的。

int vis[N], cnt, pr[N], mu[N];void sieve() {mu[1] = 1;for(int i = 2; i < N; i++) {if(!vis[i]) pr[++cnt] = i, mu[i] = -1;for(int j = 1; j <= cnt && i * pr[j] < N; j++) {vis[i * pr[j]] = 1;if(i % pr[j] == 0) break; // 此时 i * pr[j] 含至少两个 pr[j]，mu = 0mu[i * pr[j]] = -mu[i]; // mu[i * pr[j]] = mu[i] * mu[pr[j]] = -mu[i]}}}

当时间复杂度可接受时，根据 \(\mu\) 的狄利克雷卷积求逆式 \(\mathcal{O}(n\log n)\) 递推更方便。