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

每个整除值仅会被遍历一次，时间复杂度 \(\mathcal{O}(\sqrt n)\) 。

注意，当 \(i\) 的上界不等于 \(n\) 时，设其为 \(m\)，则 \(r\) 应与 \(m\) 取较小值（处理 \(n > m\) 的情况），且当 \(\left\lfloor\dfrac n i\right\rfloor = 0\) 时需要特判，直接令 \(r\) 等于 \(m\)（处理 \(n < m\) 的情况）。

4.2 扩展4.2.1 向上取整尝试将向下取整变为向上取整。
对于左边界 \(l\) ，求出使得 \(\left\lceil\dfrac n l \right\rceil = \left\lceil\dfrac n r \right\rceil\) 的最大的 \(r\) 。不妨设 \(k = \left\lceil\dfrac n l\right\rceil\)，则
\[\dfrac n r > k - 1 \Rightarrow r(k - 1) < n \Rightarrow r < \dfrac{n}{k - 1} \Rightarrow r\leq \dfrac{n-1}{k-1}\]第三步转换是因为 \(n, k\) 均为正整数。因此，只需令 \(r\gets \left\lfloor\dfrac{n - 1}{\left\lceil\frac n l\right\rceil - 1}\right\rfloor\) 即可。
注意特判 \(\left\lceil\dfrac n l\right\rceil=1\)，此时 \(r\) 的上界为无穷大，需要取实际上界。
4.2.2 高维数论分块当和式中出现若干下取整，形如
\[\sum_{i = 1} ^ n f(i) \prod_{j = 1} ^ c g\left(\left\lfloor \dfrac {n_j} {i}\right\rfloor\right)\]时，只需稍作修改，令 \(r = \min\limits_{j = 1} ^ c\left(\left\lfloor \dfrac {n_j} {\left\lfloor \frac {n_j} l\right\rfloor}\right\rfloor\right)\) 即可。不要忘记对 \(n\) 取 \(\min\) 。
时间复杂度为 \(\sum \sqrt {n_j}\) 。将使得存在 \(n_j\) 满足 \(\left\lfloor \dfrac {n_j} {i}\right\rfloor \neq \left\lfloor \dfrac {n_j} {i + 1}\right\rfloor\) 的位置 \(i\) 视作断点，则总断点数量为每个下取整式的端点数量相加而非相乘。我们只会在每相邻两个断点形成的区间处遍历一次，故有该时间复杂度。
4.3 例题I. [模拟赛] 你还没有卸载吗

给定 \(A_1, B_1, A_2, B_2, N\)，求有多少 \(x\in [1, N]\) 使得 \(B_1 + \left\lfloor\dfrac{A_1}{x}\right\rfloor = B_2 + \left\lfloor\dfrac{A_2}{x}\right\rfloor\) 。\(T\leq 2\times 10 ^ 3\)，其他所有数 \(\in [1, 10 ^ 8]\) 。时限 1s 。

考虑数论分块 \([l, r]\) 固定 \(\dfrac{A_1} x\) ，解出 \(d = \dfrac{A_2}{x}\)，反推出合法的 \(x\) 的范围：\([l, r] \cap \left[\dfrac{A_2}{d + 1} + 1, \dfrac{A_2}{d}\right]\) 。时间复杂度 \(\mathcal{O}(T\sqrt V)\) 。
另一种方法是直接二维数论分块。细节更少，且时间复杂度相同。

#include <bits/stdc++.h>using namespace std;int T, a1, b1, a2, b2, n;int main() {	cin >> T;	while(T--) {int ans = 0;cin >> a1 >> b1 >> a2 >> b2 >> n;for(int l = 1, r = 1; l <= n; l = r + 1) {r = min(n, min(a1 / l ? a1 / (a1 / l) : n, a2 / l ? a2 / (a2 / l) : n));if(b1 + a1 / l == b2 + a2 / l) ans += r - l + 1;}cout << ans << endl;	}	return 0;}

*II. CF1603C Extreme Extension数论分块优化 DP 。
一个数如何分裂由后面分裂出来的数的最小值决定，显然贪心使分出来的数尽量均匀，例如若 \(9\) 要裂成若干个比 \(4\) 小的数，那么 \(3, 3, 3\) 比 \(2, 3, 4\) 更优。
从后往前考虑，对于每个数 \(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\) 结尾的子段。
用