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

从后往前考虑，对于每个数 \(a_i\) 和值 \(j\in [1, a_i]\) ，求出有多少以 \(a_i\) 开头的子串根据上述贪心策略分裂出的最小值为 \(j\) ， \(j\) 由 \(a_i\) 分裂零次或若干次得到，记为 \(f_{i, j}\) 。
首先明确两点：

\(a_i\) 分裂成若干 \(\leq v\) 的数，最少分裂次数为 \(\left\lceil \dfrac {a_i} v \right\rceil - 1\) ，分裂成 \(\left\lceil \dfrac {a_i} v \right\rceil\) 个数。
\(a_i\) 分裂成 \(v\) 个数，这些数最小值的最大值为 \(\left\lfloor \dfrac {a_i} v \right\rfloor\) 。

考虑转移。
注意到对于固定的分裂次数，分裂出的值也是确定的。考虑枚举使得分裂次数相同的区间 \([l, r]\) ，即 \(a_i\) 整除 \([l, r]\) 内所有数向上取整的结果相同，可以通过向上取整的数论分块实现。
令 \(c = \left\lceil \dfrac {a_i} l \right\rceil\) 表示分裂出的数的个数，则分裂出的数的最小值为 \(v = \left\lfloor \dfrac {a_i} c \right\rfloor\) 。因此， \(\sum\limits_{j = l} ^ r f_{i + 1, j}\) 转移到 \(f_{i, v}\) 。
考虑在每个位置处统计该位置在所有子段中总分裂次数之和，则答案加上 \(i\times (c - 1) \times f_{i , v}\) 。其含义为，共有 \(f_{i, v}\) 个子段使得 \(a_i\) 要分裂出 \(c\) 个数，即分裂 \(c - 1\) 次。同时，若子段 \([i, k]\) 在 \(i\) 处分裂 \(c - 1\) 次，则对于任意子段 \([x, k]\) 满足 \(1\leq x\leq i\) ， \(a_i\) 分裂的次数都是 \(c - 1\) ，因为 \(a_i\) 的分裂不受前面的数的影响。
注意，当 \(c = 1\) 时， \(f_{i, v}\) 即 \(f_{i, a_i}\) 需要加上 \(1\) ，表示新增以 \(a_i\) 结尾的子段。
用 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}\) ，读者也许会好奇数学家为什么要定义如此奇怪的函数。这背后必然隐藏着其某种神秘而重要的性质。