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

具体地，令当前枚举到的 \(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\) 的前缀和。
每个整除值仅会被遍历一次，时间复杂度 \(\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\) 更优。