Number Theory Fml Bucket
Z由于不是全家桶而是半家桶,故 Family 变成了 Fml。
一、Stern-Brocot Tree
0. 前言
Stern–Brocot 树是一种维护分数的优雅的结构,包含所有不同的正有理数.这个结构分别由 Moritz Stern 在 1858 年和 Achille Brocot 在 1861 年独立发现.
上文出自 OI-wiki。
1. DIVCNT1
SP26073 DIVCNT1。
题面极其简洁,即求出:
$$\sum_{i=1}^n\sigma_0(i)$$
的值,其中 $\sigma_0(i)$ 是 $i$ 的因数个数。
直接欧拉筛然后暴力求和显然开销巨大,考虑展开 $\sigma_0(i)=\sum_{d|i}1$,于是原式化简为:
$$
\begin{aligned}
&\sum_{i=1}^n\sigma_0(i)\\
=&\sum_{i=1}^n\sum_{d|i}1\\
=&\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}1\\
=&\sum_{d=1}^n\left\lfloor\frac{n}{d}\right\rfloor\\
\end{aligned}
$$
数论分块即可做到 $\mathcal{O}(\sqrt{n})$。
I. 数论分块
普遍意义上数论分块解决的是形如 $\displaystyle\sum_{i=1}^nf(i)g(\left\lfloor\dfrac{n}{i}\right\rfloor)$ 的问题,当然也可以扩展到上取整、高维的情况,思想本质是一致的。
$\left\lfloor\dfrac{n}{i}\right\rfloor$ 只有 $\mathcal{O}(\sqrt{n})$ 个不同的取值,对于 $i\le\sqrt n$,最多只有 $\sqrt n$ 种不同的 $\left\lfloor\dfrac{n}{i}\right\rfloor$,而对于 $i>\sqrt n$,必然有 $\left\lfloor\dfrac{n}{i}\right\rfloor\le\sqrt{n}$,也最多只有 $\sqrt n$ 种不同的取值。又因为 $\left\lfloor\dfrac{n}{i}\right\rfloor$ 是非严格单调递减的,所以使 $\left\lfloor\dfrac{n}{i}\right\rfloor$ 取值相同的 $i$ 都是一个个连续段,因此我们可以逐连续段处理。
对于同一个极长连续段 $[l,r]$,$\left\lfloor\dfrac{n}{l}\right\rfloor=\left\lfloor\dfrac{n}{l+1}\right\rfloor=\cdots=\left\lfloor\dfrac{n}{r}\right\rfloor$,所以这些 $g$ 值是相等的,不妨用 $g_l$ 来表示,记 $f$ 的前缀和为 $F$,则这段连续段的贡献即为 $(F_r-F_{l-1})g_l$。
因此只要我们能 $\mathcal O(1)$ 计算 $F,g$,就可以 $\mathcal{O}(\sqrt{n})$ 计算 $\displaystyle\sum_{i=1}^nf(i)g(\left\lfloor\dfrac{n}{i}\right\rfloor)$。
对于一个极长连续段 $[l,r]$,容易说明 $r=\min\left(n,\left\lfloor\dfrac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor\right)$。若存在下一个连续段,则下一个连续段的 $l$ 即为当前连续段的 $r+1$。
对于本题,$f=1,F=g=\mathrm{id}$,数论分块容易处理。
II. Stern-Brocot Tree
但是本题的 $n$ 高达 $2^{63}$,我们需要更快的做法。
1. 化简原式
考虑 $\displaystyle\sum_{d=1}^n\left\lfloor\frac{n}{d}\right\rfloor$ 的几何意义。考虑反比例函数 $y=\dfrac{n}{x}$ 的图像。

绿线即为 $y=\dfrac{n}{x}$ 的图像,而根据要求的式子,答案则是该图像下正整数点的数量,即可视作为蓝线下的面积, 毕竟一个正整数格点和一个单位方格是一一对应的。

如上图所示,数论分块其实就是在同高的蓝框内拆矩形,并快速计算矩形面积。
现在我们考虑优化。
我们先假定 $n$ 不是完全平方数,然后对原式进行拆分, $\displaystyle\sum_{d=1}^n\left\lfloor\frac{n}{d}\right\rfloor=\displaystyle\sum_{d=1}^{\lfloor\sqrt{n}\rfloor}\left\lfloor\frac{n}{d}\right\rfloor+\displaystyle\sum_{d=\lfloor\sqrt{n}\rfloor+1}^{n}\left\lfloor\frac{n}{d}\right\rfloor$,而:
$$
\begin{aligned}
&\sum_{d=\lfloor\sqrt{n}\rfloor+1}^{n}\left\lfloor\frac{n}{d}\right\rfloor\\
=&\sum_{d=\lfloor\sqrt{n}\rfloor+1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}1\\
=&\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}\sum_{\lfloor\sqrt{n}\rfloor<d\le n\land \left\lfloor\frac{n}{d}\right\rfloor\ge i}1\\
=&\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}\sum_{\lfloor\sqrt{n}\rfloor<d\le n\land \left\lfloor\frac{n}{i}\right\rfloor\ge d}1\\
=&\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}\sum_{d=\lfloor\sqrt{n}\rfloor+1}^{\left\lfloor\frac{n}{i}\right\rfloor}1\\
=&\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}(\left\lfloor\frac{n}{i}\right\rfloor-\lfloor\sqrt{n}\rfloor)\\
=&\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}\left\lfloor\frac{n}{i}\right\rfloor-(\lfloor\sqrt{n}\rfloor)^2\\
\end{aligned}
$$
代入原式,得到 $\displaystyle\sum_{d=1}^n\left\lfloor\frac{n}{d}\right\rfloor=2\displaystyle\sum_{d=1}^{\lfloor\sqrt{n}\rfloor}\left\lfloor\frac{n}{d}\right\rfloor-(\lfloor\sqrt{n}\rfloor)^2$。对于 $n$ 是完全平方数的情况,这个式子是完全一致的,只是推导过程有一部分加一减一的变化。
因此我们将问题规约为求 $\displaystyle\sum_{d=1}^{\lfloor\sqrt{n}\rfloor}\left\lfloor\frac{n}{d}\right\rfloor$ 的值。
由于 $\displaystyle\sum_{d=\lfloor\sqrt{n}\rfloor+1}^{n}\left\lfloor\frac{n}{d}\right\rfloor=\displaystyle\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}\left\lfloor\frac{n}{i}\right\rfloor-(\lfloor\sqrt{n}\rfloor)^2$,则 $\displaystyle\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}\left\lfloor\frac{n}{i}\right\rfloor=\displaystyle\sum_{d=\lfloor\sqrt{n}\rfloor+1}^{n}\left\lfloor\frac{n}{d}\right\rfloor+(\lfloor\sqrt{n}\rfloor)^2$。我们要算的即为下图的正整数点个数,或可视为面积。

当然,简便的理解方法是,考虑最终要求的整个部分,容易证明其关于 $y=x$ 是对称的,所以直接将 $\displaystyle\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}\left\lfloor\frac{n}{i}\right\rfloor$ 的部分沿 $y=x$ 翻转即可得到 $\displaystyle\sum_{d=\lfloor\sqrt{n}\rfloor+1}^{n}\left\lfloor\frac{n}{d}\right\rfloor+(\lfloor\sqrt{n}\rfloor)^2$ 。
注意“面积”是辅助理解的,实际上我们数的是正整点数量,同时我们发现正整点对应着一个单位正方形的右上角。
2. 构造凸包
考虑构造一个凸包,如下图所示。

这个凸包的定义是 $\mathrm{conv}\{(x,y)\in\mathbb{Z}^2|xy>n,\left\lfloor\frac{n}{\lfloor\sqrt{n}\rfloor}\right\rfloor\le x\le n+1,1\le y\le\lfloor\sqrt{n}\rfloor+1\}$ 其必然存在。
这个凸包具有如下性质:
- 凸包下边界的每一个顶点都是整点,且这些整点都在 $y=\dfrac{n}{x}$ 的严格上方。
- 凸包下边界与蓝框边界之间(不含两个边界上的整点)不存在任何整点。
- 在符合上述条件的前提下,该凸包下边界从左上到右下每一条向量的斜率绝对值都尽可能的小。
:::info[三条性质为何成立?]
- 性质一直接根据定义得到。
- 性质二也几乎直接根据定义得到,在矩形 $[1,n]\times[1,\lfloor\sqrt{n}\rfloor]$ 中,所有的点要么在凸包内,要么在蓝框内,即我们的计算范围内。
- 性质三可以做反证,如果对于某条向量的右端点,不取使其斜率绝对值最小的点,那根据凸包的性质,这个点必然在凸包内部而不在凸包边界上。
:::
由于后面的步骤,我们希望构成凸包下边界的所有向量都满足,其 $\Delta x$ 与 $\Delta y$ 互质。
如果有不互质的,我们会人为的将其拆成 $\gcd(\Delta x,\Delta y)$ 条长度相等,方向相同的向量即可,参考上图所示凸包下边界的第一条与第二条向量,斜率相同但被拆成两条。
这样一是保证了后面 Stern-Brocot Tree 对其的维护,二是使得一个向量内仅端点为整点。
为什么凸包的上边界是 $y=\lfloor\sqrt{n}\rfloor+1$,左边界是 $x=\left\lfloor\frac{n}{\lfloor\sqrt{n}\rfloor}\right\rfloor$ ? 参考上图,第一条向量的设置看起来十分多余。
我们的计算逻辑是,对于每个向量 $\vec{v}$,计算其“左边”“上开下闭”区域的整点数,

对于上图,第一至四条向量处理的分别为灰线、绿线、橙线、紫线上的正整数点。
因此第一条向量是必要的。
现在考虑一条边的贡献。

不包含上边界(我们前面已经提到该结构维护的是上开下闭的点集)与 $y$ 轴上的点(非正整数),左侧矩形贡献的有效正整点数为 $xq$。
右侧三角形的贡献不容易直接得出,我们先给出一个引理:
:::info[Pick 定理]
给定顶点均为整点的简单多边形,Pick 定理说明了其面积 $A$ 和内部格点数目 $i$、边上格点数目 $b$ 的关系:$A=i+\dfrac{b}{2}-1$。
:::
边上与内部的点总贡献即为 $i+b=A+\dfrac{b}{2}+1$,由于是三角形,则 $A=\dfrac{qp}{2}$,又因为 $\gcd(q,p)=1$,斜边上只有端点是整点,故可算得 $b=p+q+1$。
整理得 $i+b=\dfrac{1}{2}(qp+q+p+1)+1$,再加上矩形的 $xq$,减去重复贡献,即三角形与矩形相交的那条边上 $q$ 个点,再减去不应记入贡献的 $2$ 个点 $(x,y),(x+p,y-q)$,最终整个向量的贡献即为 $\dfrac{1}{2}(qp+q+p+1)+1+xq-q-2$,化简得到下式:
$$
xq+\frac{1}{2}(p-1)(q+1)
$$
3. Stern-Brocot 树上二分
现在我们已经知道了解法的框架,只需要知道该如何快速算出构成凸包下边界的每个向量是什么,就可以解决原问题了!
引入 Stern-Brocot 树这个结构。
首先要定义 Stern-Brocot 序列,它是无穷个有理数序列的总称,其中第 $k$ 个序列(编号从 $0$ 开始)被称作第 $k$ 阶 Stern-Brocot 序列。
递归地定义它:设第 $k$ 阶 Stern-Brocot 序列为: $$\{\dfrac{a_1}{b_1},\dfrac{a_2}{b_2},\cdots,\dfrac{a_n}{b_n}\}$$则第 $(k+1)$ 阶 Stern-Brocot 序列即为:
$$
\{\dfrac{a_1}{b_1},\dfrac{a_1+a_2}{b_1+b_2},\dfrac{a_2}{b_2},\dfrac{a_2+a_3}{b_2+b_3},\cdots,\dfrac{a_{n-1}+a_{n}}{b_{n-1}+b_{n}},\dfrac{a_n}{b_n}\}
$$
通俗地说,就是在第 $k$ 阶 Stern-Brocot 序列每相邻两项 $\{\dfrac{a_{i}}{b_{i}},\dfrac{a_{i+1}}{b_{i+1}}\}$ 之间插入一个新的有理数 $\dfrac{a_{i}+a_{i+1}}{b_{i}+b_{i+1}}$,这样就得到了第 $(k+1)$ 阶 Stern-Brocot 序列。尽管中位分数的定义本身允许分数的约分,但是在 Stern–Brocot 序列的构造中,只需要直接将分子和分母分别相加即可,而不必担心约分的问题,这个事情我们将会在后文给出证明。
递归的起点是第 $0$ 阶 Stern-Brocot 序列 $\{\dfrac{0}{1},\dfrac{1}{0}\}$,这两项将是所有 Stern-Brocot 序列的第一项和最后一项。
注意 $\dfrac{1}{0}$ 在此处可视作正无穷。
由此,可以迭代地构造出所有阶的 Stern–Brocot 序列.前几次迭代的结果如下:
$$
\begin{array}{ccccccccc}
&&&\dfrac{0}{1}, & \dfrac{1}{1}, & \dfrac{1}{0} &&&\\\\
&&\dfrac{0}{1}, & \dfrac{1}{2}, & \dfrac{1}{1}, & \dfrac{2}{1}, & \dfrac{1}{0} &&\\\\
\dfrac{0}{1}, & \dfrac{1}{3}, & \dfrac{1}{2}, & \dfrac{2}{3}, & \dfrac{1}{1}, & \dfrac{3}{2}, & \dfrac{2}{1}, & \dfrac{3}{1}, & \dfrac{1}{0}
\end{array}
$$
将每次迭代中新添加的分数连结成树状结构,就得到了 Stern–Brocot Tree。如下图所示:

发现 Stern–Brocot Tree 深度为 $k$ 的树上节点从左到右排列,就是第 $k$ 阶 Stern-Brocot 序列的全体偶数项。
另一种等价的构造方式是以三元组
$$
\left(\dfrac{0}{1},\dfrac{1}{1},\dfrac{1}{0}\right)
$$
作为根节点,且在每个节点
$$
\left(\dfrac{a}{b},\dfrac{p}{q},\dfrac{c}{d}\right)
$$
后都分别添加
$$
\left(\dfrac{a}{b},\dfrac{a+p}{b+q},\dfrac{p}{q}\right),\ \left(\dfrac{p}{q},\dfrac{p+c}{q+d},\dfrac{c}{d}\right)
$$
为左右子节点,就可以构造出整个 Stern–Brocot Tree。Stern–Brocot Tree 的每个节点记录的三元组中,实际存储的分数是位于三元组中间的分数 $\dfrac{p}{q}$,而左右两个分数 $\dfrac{a}{b}$ 和 $\dfrac{c}{d}$ 是更早就出现过的分数.而且,考虑前一种构造就会发现,分数 $\dfrac{p}{q}$ 正是通过插入 $\dfrac{a}{b}$ 和 $\dfrac{c}{d}$ 的中位分数得到的。
三元组构造意味着每个 Stern–Brocot 树上的节点都对应着一个矩阵:
$$
S = \begin{pmatrix}
b & d\\
a & c
\end{pmatrix}
$$
Stern–Brocot 树的根节点是单位矩阵 $I$,而向左子节点移动和向右子节点移动则分别对应将当前节点矩阵右乘以矩阵
$$
L=\begin{pmatrix}
1 & 1 \\
0 & 1
\end{pmatrix},~
R=\begin{pmatrix}
1 & 0 \\
1 & 1
\end{pmatrix}.
$$
每个节点实际对应的分数就是 $f(S)=\dfrac{a+c}{b+d}$ .每个节点的矩阵 $S$ 都可以写成一系列矩阵 $L$ 和 $R$ 的乘积,这也可以理解为是由 $L$ 和 $R$ 构成的字符串,表示了从根节点到达它的路径.将所有正的有理数唯一地表示为这样的字符串,这可以看作得到了正有理数的一种表示,故而也称作 Stern–Brocot 数系(Stern–Brocot number system)。
接下来讨论 Stern–Brocot Tree 的性质。简而言之,Stern–Brocot Tree是包含所有正的最简有理分数的二叉搜索树,它也是分子和分母的堆,也是分母和分子构成的二元组的笛卡尔树。如果考虑前文的三元组构造中的左右端点形成的区间,则 Stern–Brocot Tree 也可以看作是 $[0,\infty]$ 上的线段树。这些陈述可以通过如下的三条基本性质导出:
【单调性】
每一层的分数都是单调递增的.为此只需要归纳证明.因为如果 $\dfrac{a}{b} < \dfrac{c}{d}$,那么必然有
$$
\dfrac{a}{b} < \dfrac{a+c}{b+d} < \dfrac{c}{d}.
$$
这一点可以通过消去不等式的分母得出.归纳起点是 $\dfrac{0}{1} < \dfrac{1}{0}$,单调性也显然成立.
【最简性】
在上面的构造中,每个分数都是最简分数。为此同样需要归纳证明上面的构造中,每一层相邻的分数 $\dfrac{a}{b}$ 和 $\dfrac{c}{d}$ 都满足等式:
$$
bc-ad = \begin{vmatrix}
b & d\\
a & c
\end{vmatrix} = 1.
$$
根节点处是单位矩阵,这显然成立.向下移动时,乘以的矩阵 $L$ 和 $R$ 的行列式都是 $1$,根据行列式的性质可知,在下一层同样成立
$$
\begin{vmatrix}b & b+d \\ a & a+c \end{vmatrix} = \begin{vmatrix}b+d & d \\ a+c & c\end{vmatrix} = 1.
$$
对于归纳起点 $\dfrac{0}{1}$ 和 $\dfrac{1}{0}$ 这也是显然的。由此,根据裴蜀定理,必然可知每个分数的分子和分母都是互素的,即所有分数都是最简分数。
【完全性】
最后,需要说明 Stern–Brocot 树包括了所有正的最简分数.因为前两条性质已经说明 Stern–Brocot 树是二叉搜索树,而任何正的最简分数 $\dfrac{p}{q}$ 必然位于 $\dfrac{0}{1}$ 和 $\dfrac{1}{0}$ 之间,根据二叉搜索树上做搜索的方法,二叉搜索树上没有 $\dfrac{p}{q}$ 的唯一可能性就是搜索过程无限长。下面将证明,对于任意正有理数 $\dfrac{p}{q}$,无限长的搜索过程是不可能的。
设搜索过程中得到的 $\dfrac{p}{q}$ 的下界为 $\dfrac{a}{b}$,上界为 $\dfrac{c}{d}$ 。下界初始值为 $\dfrac{0}{1}$,上界初始值为 $\dfrac{1}{0}$,随后上下界通过 $\dfrac{a+c}{b+d}$ 和 $\dfrac{p}{q}$ 的比较结果逐步调整。若搜索无限长,则每一步都有:
$$
\dfrac{a}{b} < \dfrac{p}{q} < \dfrac{c}{d}
$$
那么必然在无限步内都有:
$$
bp-aq \ge 1,\ cq-dp \ge 1
$$
将两个不等式分别乘以 $(c+d)$ 和 $(a+b)$,得到:
$$
(c+d)(bp-aq) + (a+b)(cq-dp) \ge a+b+c+d
$$
利用前面已经说明的等式 $bc-ad=1$ 可将上式化简为:
$$
p+q \ge a+b+c+d
$$
然而,每次搜索更深入一层的时候,不等式右侧都严格地增加,而左侧保持不变,因此上述条件无法在无限步内成立.因此,搜索过程会在有限步内停止。
有多种 Stern-Brocot 树上查找给定分数 $\dfrac{p}{q}$(即找出在树上走到该点的路径)的算法,例如通过连分数的方法可以做到 $\mathcal O(\log \min\{p,q\})$,但是此题中要寻找的分数是事先不知道的,因此我们暂时跳过查找给定分数的算法,直接回到原题。
我们希望找到构成凸包的各向量,考虑从起点开始,寻找第一条向量(向量方向从左上到右下),然后沿着该向量移动,以这条向量的末尾为起点再寻找第二条向量,以此类推。
那么我们就需要解决这样的问题:以 $(x,y)$ 为起点,找到下一条向量。
由于向量的端点都必须是整点,所以它的斜率一定是一个有理数 $\dfrac{p}{q}$。
为何这个答案是可二分的,即如何说明在 Stern-Brocot Tree 上二分的正确性?首先 Stern-Brocot 序列具有单调性,根据前面的性质,答案 $\dfrac{p}{q}$ 必然是存在的,然后设 $\dfrac{p}{q}$ 的深度为 $k$,那么二分过程的本质就是在第 $k$ 阶 Stern-Brocot 序列中进行二分,因为到第 $k$ 层遇到 $\dfrac{p}{q}$ 自然会停止,且小于 $k$ 阶的都被包含在第 $k$ 阶中。
然后考虑第 $k$ 阶 Stern-Brocot 序列中的每一个分数,其中小于等于 $\dfrac{p}{q}$ 的所有分数 $\dfrac{p'}{q'}$,如果斜率的绝对值取它们,那么得到的 $(x+p',y-q')$ 必然在双曲线上方(且不合法,因为此时 $(p',-q')$ 这条向量下方必然还涵盖了 $(x+p,y-q)$ 这个不该被统计的整点)。
其中大于 $\dfrac{p}{q}$ 的分数 $\dfrac{p''}{q''}$ ,那么得到的 $(x+p'',y-q'')$ 必然在双曲线下方, 考虑如果存在一个 $\dfrac{p''}{q''}$,那么应该二分到它,而不是 $\dfrac{p}{q}$,因为此时 $\dfrac{p}{q}$ 根本不合法。
最终的一步,既然每一层都具有这样的单调性,我们怎么说明我们二分出的答案是最优的,不会在下一层继续产生更优的呢?我们会在后文构造性的说明判断二分停止的条件, 使得确定 $\dfrac{p}{q}$ 是最终答案。
综上我们说明了 $\dfrac{p}{q}$ 必然可以在 Stern-Brocot Tree 中二分地找到。
现在考虑具体过程。
根据前文的讨论,我们以 $(\left\lfloor\dfrac{n}{\lfloor\sqrt{n}\rfloor}\right\rfloor,\lfloor\sqrt{n}\rfloor)$ 作为二分的起点,初始时二分的上下界为 $r=\dfrac{0}{1},l=\dfrac{1}{1}$,从向量的角度考虑就是 $\vec{R}=(1,0),\vec{L}=(1,-1)$。(注意是命名是反过来的,更符合直觉,且 $\Delta y$ 要取负)
每次取中点,设此时的 $l=\dfrac{a}{b},r=\dfrac{c}{d}$,则有 $\mathrm{mid}=\dfrac{a+c}{b+d}$,从向量的角度就是 $\vec{M}=(b+d,-a-c)$,本质就是简单地向量相加。其实 Stern-Brocot Tree 的体现就仅仅是这一步取中位分数罢了,但是我们把这个过程具象成树形后,得到了许多优美的性质,这些性质才保证了这一步的正确性,体现了这一步的精妙。
具体二分的过程很简单:
- 如果从目前的位置为起点,$\vec{M}$ 的终点在双曲线的上方,那么令 $\vec{R}\gets\vec{M}$。
- 如果 $\vec{M}$ 的终点在双曲线的下方,那么令 $\vec{L}\gets\vec{M}$。
二分的终止条件是什么?
曲线的函数表达式为 $f(x)=\dfrac{n}{x}$,其导数为 $f'(x)=-\dfrac{n}{x^2}$。
当 $\vec{M}$ 的终点在曲线下方时,若 $\dfrac{\vec{R}_y}{\vec{R}_x}\le f'(x+\vec{M}_x)$,即 $-(x+\vec{M}_x)^2 \vec{R}_y\ge n\vec{R}_x$,则之后二分到的点无论如何都会在曲线下方,此时应终止二分。而 $\vec{R}$ 就是我们要找的下一个向量。
:::info[证明该终止条件的正确性]
证明: 设 $\vec M,\vec R$ 为当前 Stern-Brocot 区间的两个边界方向,且 $\vec R$ 为二分得到的边界。由于 Stern-Brocot Tree 的性质,$\vec R$ 之后的任意候选方向 $\vec V$ 均可写为:
$$
\vec V=a\vec M+b\vec R,\qquad a,b\ge0
$$
于是:
$$
\frac{V_y}{V_x}=\frac{aM_x\frac{M_y}{M_x}+bR_x\frac{R_y}{R_x}}{aM_x+bR_x}
$$
即 $\frac{V_y}{V_x}$ 是 $\frac{M_y}{M_x}$ 与 $\frac{R_y}{R_x}$ 的加权平均。由于这些方向按 Stern-Brocot 顺序排列,故 $\vec R$ 之后的方向均满足:
$$
\frac{V_y}{V_x}\le\frac{R_y}{R_x}
$$
设 $\vec M$ 的终点为:
$$
P=(X,Y)=(x+M_x,y+M_y)
$$
且 $P$ 位于双曲线 $f(x)=n/x$ 下方,即 $Y\le f(X)$,若:
$$
\frac{R_y}{R_x}\le f'(X)=-\frac{n}{X^2}
$$
则对任意 $t\ge0$,由 $f$ 的凸性,
$$
f(X+tR_x)\ge f(X)+tf'(X)R_x.
$$
又因为 $Y\le f(X), R_y\le f'(X)R_x$,所以:
$$
Y+tR_y
\le f(X)+tf'(X)R_x
\le f(X+tR_x)
$$
故从 $P$ 沿 $\vec R$ 的整条射线均位于双曲线下方。
同理,由于 $\vec R$ 之后的任意方向 $\vec V$ 均满足
$$
\frac{V_y}{V_x}\le\frac{R_y}{R_x}\le f'(X),
$$
这些方向的射线也均不会越过双曲线。因此 $\vec R$ 之后不存在更优的候选方向,结合二分维护的边界不变量,$\vec R$ 即为所求的下一向量。
:::
4. 单调栈
由于我们维护的是凸包,斜率的绝对值要递减,同时要优化时间复杂度,我们要仔细考虑每次二分的上下界。
考虑优化。开一个存储向量的单调栈,向量斜率的绝对值从栈底到栈顶单调递增。
初始时,往栈中先后加入向量 $(1,0)$ 与 $(1,1)$。
每次从 $(x,y)$ 开始时,先取出栈顶向量(也就是上一步找到的可行的向量),记为 $\vec{L}$。
若 $(x,y)+\vec{L}$ 在曲线上方,则令 $(x,y)\gets(x,y)+\vec{L}$ 并计算贡献,继续判断新的 $(x,y)+\vec{L}$ 是否在曲线上方;否则退出循环。这一步的本质就是我们先前所说的,如果有两个方向增量不互质的,我们会人为的将其拆成 $\gcd(\Delta x,\Delta y)$ 条长度相等,方向相同的向量。这个循环执行多次便意味着 $\vec{L}$ 被重复了多次。由于斜率的绝对值要递减,所以如果能重复 $\vec{L}$ 还合法,那么选择重复显然是最优的, 且在初始时容易证明 $(1,-1)$ 是最优的。
设当前栈顶为 $\vec{R}$。
若 $(x,y)+\vec{R}$ 在曲线下方,则令 $\vec{L}\gets \vec{R}$,进行弹栈,并令 $\vec{R}$ 为新的栈顶,继续判断新的 $(x,y)+\vec{R}$ 是否在曲线下方;否则退出循环。
这个过程的极端情况就是一直弹栈,最终 $\vec{R}=(1,0)$,而 $(1,0)$ 无论怎样都不会出栈。
然后在 $\vec{L}$ 与 $\vec{R}$ 之间二分即可。二分过程中,若 $(x,y)+\vec{M}$ 在曲线上方,则将 $\vec{M}$ 加入单调栈,显然这样加入的 $\vec{M}$ 是递减的,不会破坏单调栈的性质。
以上就是整个的计算流程,当然这还没有结束。
5. 复杂度
记 $l=\dfrac ab$、$r=\dfrac cd$,对应的向量为 $\vec L=(b,-a)$、$\vec R=(d,-c)$,则 $\vec M=\vec L+\vec R=(b+d,-a-c)$。整个过程围绕
$$\sigma=\vec M_x=b+d$$
展开。把“取栈顶 $\vec L$、重复 $\vec L$、弹栈得到 $\vec R$、二分确定下一条向量”这一循环体称作一轮。
引理 1. 任何时刻 $ad-bc=1$。
证明: 初始 $l=\dfrac11,r=\dfrac01$ 时有 $ad-bc=1\cdot1-1\cdot0=1$。更新 $\vec L\gets\vec L+\vec R$ 把 $(a,b)$ 换成 $(a+c,b+d)$,更新 $\vec R\gets\vec L+\vec R$ 把 $(c,d)$ 换成 $(a+c,b+d)$,两者都保持 $ad-bc$ 不变。
引理 2. 任何时刻 $b\le x-1$、$d\le n-x+1$,从而 $\sigma\le n$。
证明: $\vec L$ 是刚走过的凸包边的方向,这条边的起点横坐标为 $x-b$,它是遍历中到过的顶点,故 $x-b\ge 1$;$\vec R$ 的终点横坐标为 $x+d$,不越过构造凸包所用矩形的右边,故 $x+d\le n+1$。两式相加即得 $\sigma\le n$。
引理 3. 每次二分使 $\sigma$ 至少增加 $1$。
证明: $\vec L\gets\vec L+\vec R$ 时 $\sigma$ 由 $b+d$ 变为 $(b+d)+d=\sigma+d$;$\vec R\gets\vec L+\vec R$ 时变为 $b+(b+d)=\sigma+b$。两种情形都至少增加 $1$。
由引理 3,若第 $i$ 轮首、轮末的 $\sigma$ 为 $s_i,e_i$,则该轮内二分的次数不超过 $e_i-s_i$。沿 $\vec L$ 平移一次使 $x$ 增加 $b\ge1$,而 $x$ 单调不减且不超过 $n+1$,故平移次数不超过 $n$;弹栈次数不超过入栈次数,而入栈只发生在二分中令 $\vec R\gets\vec L+\vec R$ 时。
只需再估计 $\displaystyle\sum_i(e_i-s_i)$。设第 $i$ 轮末 $\vec L,\vec R$ 的横坐标为 $u_i,v_i$,第 $i$ 轮首栈顶向量(即该轮第一次二分中的 $\vec R$)的横坐标为 $w_i$。轮首的 $\vec L$ 就是上一轮确定的向量,横坐标为 $v_{i-1}$,于是:
$$s_i=v_{i-1}+w_i,\qquad e_i=u_i+v_i,$$
合并得:
$$e_i-s_i=(u_i-v_{i-1})+(v_i-w_i).$$
一轮内 $\vec R$ 只增不减,故 $w_i\le v_i$;又 $v_i$ 是下一轮平移所用的方向,至少把 $x$ 推进 $v_i$,故 $\displaystyle\sum_i v_i\le n$。因此
$$\sum_i(v_i-w_i)\le\sum_i v_i\le n .$$
再看 $\displaystyle\sum_i(u_i-v_{i-1})$,它是各轮中 $\vec L$ 横坐标总增量之和。若第 $i$ 轮以入栈结束,最后入栈的是 $\vec L+\vec R$,其横坐标 $u_i+w_{i+1}$ 就是 $v_i$,故 $u_i\le v_i$。若第 $i$ 轮以终止条件结束,则本轮没有再入栈,$u_i$ 至多比 $v_i$ 多出栈中相邻向量的横坐标 $w_{i+1}$,仍有 $u_i\le v_i+w_{i+1}$。于是在每一轮都有 $u_i\le v_i+w_{i+1}$,求和得:
$$\sum_i(u_i-v_{i-1})\le\sum_i(v_i+w_{i+1}-v_{i-1})=v_N-v_0+\sum_i w_{i+1}\le n+n .$$
(以终止条件结束的轮中,$u_i$ 可能比 $v_i+w_{i+1}$ 略大,但这样的超出量之和是 $o(n)$ 所以不影响结论)
两式相加得 $\displaystyle\sum_i(e_i-s_i)\le 3n$。三类操作的次数都是 $\mathcal{O}(n)$,所以算法总复杂度为 $\mathcal{O}(n)$。
竟然是线性,甚至劣于数论分块。
不过接下来仅需要一步简单的优化就可以迅速降低复杂度。
6. 分治
我们考虑一个阈值 $B$,先按刚才的方法找向量,直到目前点的 $y<B$,停止,剩下的直接暴力求值,暴力的部分沿 $y=x$ 翻转得到 $\sum_{i=1}^{B}\left\lfloor\dfrac{n}{i}\right\rfloor$。
论文 [1] 中证明了 $B=n^{\frac13}$ 是量级最优,此时复杂度为:
$$O\left(n^{\frac13}\log n\right)$$
因此我们就以这个极其优异的复杂度解决了这个问题。
7. 代码
代码非常简洁,注意本题需要 __int128。
1 | |
III. What’s More…
就在前段时间(2026 年 9 月 28 日,以论文中标注日期为准),清华求真书院的 Darren Li(w33z8kqrqk8zzzx33)在论文 [2] 中提出了全新的基于 Voronoï 求和的解析算法,将该问题做到了期望时间复杂度 $\mathcal{O}(n^{\frac{9}{28}+o(1)})$,不过该算法仅理论复杂度更优,难以投入实际应用。
论文中作者明确说明:“AI disclosure. The core contribution is due to LLMs. We simplified the resulting proof.”(人工智能披露。核心贡献归功于大型语言模型。我们简化了由此得出的证明)
2. AFS3
SP33039 AFS3。
求出:
$$\sum_{i=1}^n(\sigma_1(i)-i)$$
的值,其中 $\sigma_1(i)$ 是 $i$ 的因数和。
I. 化简原式
先转换式子,本题的推导过程会在不省略关键步骤或观察的前提下相对简略一些:
$$
\begin{aligned}
&\sum_{i=1}^n(\sigma_1(i)-i)\\
=&\sum_{i=1}^n\sum_{d|i}d-\frac{n(n+1)}{2}\\
=&\sum_{d=1}^nd\left\lfloor\frac{n}{d}\right\rfloor-\frac{n(n+1)}{2}\\
\end{aligned}
$$
问题归约于求 $\displaystyle\sum_{i=1}^ni\left\lfloor\frac{n}{i}\right\rfloor$,数论分块显然也可以做到单组询问 $\mathcal{O}(\sqrt{n})$。
考虑其几何意义,问题从双曲线下正整数点计数变为双曲线下正整数点权值和,其权值为其横坐标。
与上一题类似,我们将做贡献部分的图像分成三部分:

正方形边长还是 $\lfloor\sqrt{n}\rfloor$,设其为 $m$。
由上题我们得知紫色部分正整点数与橙色部分正整点数相同,且每个紫色部分的正整点关于 $y=x$ 的对称点都在橙色部分中,不重不漏,而紫色部分整点的横坐标做对称后便称为橙色部分的纵坐标。
因此我们可以得出,整个紫色+蓝色部分的贡献,等于橙色+蓝色部分的以纵坐标为权值的贡献。于是我们只需计算橙色+蓝色区域以横纵坐标和为权值的贡献,再将重复计算的一个蓝色区域贡献减去即可。
容易计算出蓝色正方形的贡献为 $\dfrac{1}{2}m^2(m+1)$。
现在我们需要计算的便是橙色+蓝色区域分别以横纵坐标为权值的贡献。
II. 计算向量贡献
我们依旧使用维护凸包的方法,由于双曲线没有变化,变化的只是每个整点的权值,因此构成凸包的这些向量都没有变,变的只有每个向量的贡献。

由此图,向量的横纵坐标贡献可拆分为:
$$
\begin{cases}
\text{Row}={\color{#00aaff}{\dfrac{qx(x-1)}{2}}}+{\textcolor{#8800ff}{R_{\triangle}}}-(2x+p)\\
\text{Col}={\color{#00aaff}{\dfrac{(x-1)q(2y-q-1)}{2}}}+{\textcolor{#8800ff}{C_{\triangle}}}-(2y-q)
\end{cases}
$$
最后一项为减去向量两端点的贡献。计算中矩形同时不取上边界(上闭下开),左边界(为坐标轴,不计入贡献),右边界(让相交部分贡献由三角形来计算)。
现在考虑三角形的贡献如何计算。
Naive 的做法是直接计算三角形贡献,其式子为:
$$
\begin{cases}
\text{Row}_{\triangle}=\displaystyle\sum_{i=0}^p(\left\lfloor\dfrac{qi}{p}\right\rfloor+1)(x+p-i)\\
\text{Col}_{\triangle}=\displaystyle\sum_{i=0}^q(\left\lfloor\dfrac{pi}{q}\right\rfloor+1)(y-i)\\
\end{cases}
$$
然后直接用类欧 $\mathcal{O}(\log n)$ 计算,类欧的具体算法参见后续章节。
不过这样凭空多了一只 $\log$,我们希望得到一个 $\mathcal O(1)$ 计算向量对三角形贡献的做法。
我们维护的所有向量,由于是在 Stern-Brocot Tree 上二分得到的,故除了最初的 $(1,-1)$ 外,其余都是由某两个向量相加而形成的。
那我们不妨考虑实现一个类似 pushup 的操作,使得二分的过程中 $\vec{M}$ 的贡献能由 $\vec{L},\vec{R}$ 的贡献合并得到。

考虑将 $\vec{R}$ 的起点移动到 $\vec{L}$ 的终点,这样首尾相接即可得到 $\vec{M}$,$\vec{M}$ 所贡献的部分即为青色,紫色和蓝色三部分贡献之和(注意紫色矩形不取满,这样不计算重边),减去单点 $B$ 的贡献(被计算两次)。
$\triangle ABC$ 内部(不包含三个顶点)没有整点,故没有贡献。
这其实是易于理解的,回顾寻找向量的过程,容易发现任何一次二分过程的 $l,r$ 都是某一阶 Stern-Brocot 序列的相邻两个分数。如果 $\triangle ABC$ 内部有一个顶点 $F$,那么由斜率推导,向量 $\overrightarrow{AF}$ 的对应分数 $f$ 必然被夹在 $l,\mathrm{mid}$ 之间,故 $\overrightarrow{AF}$ 必能表示成 $x\vec{L}+y\vec{M}$,由于 $x,y\in\mathbb{N}^+$,$F$ 是必然在 $\triangle ABC$ 之外,与前面的反设矛盾。因此 $\triangle ABC$ 内部无贡献。
设 $A(x,y)$,$\vec{L}(p_L,q_L),\vec{R}(p_R,q_R)$。
紫色矩形的贡献是容易计算的,为:
$$
\begin{cases}
\text{Row}_{\square}=-\dfrac{q_Rp_L(2x+p_L-1)}{2}\\
\text{Col}_{\square}=-\dfrac{p_Lq_R(2y+2q_L+q_R-1)}{2}
\end{cases}
$$
然后考虑两个小三角形的贡献,由于权值是横纵坐标,向量的位置会影响三角形贡献的权值,因此我们观察向量在平移时贡献的改变量。
容易得出,其向 $x$ 轴正方向移动 $1$,其以横坐标为权值的贡献增加量即为三角形的点数,向 $y$ 轴正方向移动 $1$,其以纵坐标为权值的贡献增加量即为三角形的点数。
因此我们只需要维护每个向量在特定位置的贡献以及其对应三角形的整点数即可,后者的计算方法即运用 Pick 定理,上一题中已提到。为了方便,这个特定位置选取为使三角形上方顶点为原点的位置。
综上,对于一个向量 $\vec{v}$ 的对应三角形我们需要维护三个值:$\pi_v,\alpha_v,\beta_v$,分别代表将三角移动至上方顶点与原点重合时,其内部及边界的整点数、以横坐标为权值的贡献,以纵坐标为权值的贡献。
注意在计算这个贡献的时候,由于三角形实际上是平移之后计算的,所以我们不应忽略坐标轴上的点的贡献。
三者的转移由上文已经明确:
$$
\begin{cases}
\pi_M={\color{#009999}\pi_L}+{\color{#00aaff}\pi_R}+{\color{#8800ff}p_Lq_R}-1\\
\alpha_M={\color{#009999}\alpha_L}+{\color{#00aaff}\alpha_R+p_L\pi_R}+{\color{#8800ff}\dfrac{q_R(p_L-1)p_L}{2}}-p_L\\
\beta_M={\color{#009999}\beta_L}+{\color{#00aaff}\beta_R-q_L\pi_R}-{\color{#8800ff}\dfrac{p_L(2q_L+q_R+1)q_R}{2}}+q_L\\
\end{cases}
$$
转移的起点即为向量 $(1,0)$ 和 $(1,1)$。
注意实际计算向量贡献的时候,横纵坐标为权值的贡献要分别加上 $\pi_M$ 乘相应方向的平移量。
凸包的遍历与上一题一致,$y\le n^{\frac{1}{3}}$ 的暴力即分别计算 $\displaystyle\sum_{i<y} i\lfloor \frac{n}{i}\rfloor$ 和 $\displaystyle\sum_{i<y}\frac{1}{2}\lfloor \frac{n}{i}\rfloor(\lfloor \frac{n}{i}\rfloor+1)$,也就是剩下部分横纵坐标的贡献。
由于合并向量贡献是常数复杂度,故复杂度不变:$\mathcal{O}(n^{\frac{1}{3}}\log n)$。
References
[1] Alcántara D, Blanco M, Criado F, Santos F. On the convex hull of integer points above the hyperbola[EB/OL]. arXiv: 2501.19193, 2025. https://arxiv.org/abs/2501.19193.
[2] Li D. Computing the divisor summatory function in $N^{9/28+o(1)}$[EB/OL]. arXiv: 2609.29949, 2026. https://arxiv.org/abs/2609.29949.
[3] OI-wiki. Stern–Brocot tree[EB/OL]. https://oi-wiki.org/math/number-theory/stern-brocot/.
[4] Rigel. SP26073 DIVCNT1 - Counting Divisors[EB/OL]. 洛谷专栏, 2025-12-19. https://www.luogu.com.cn/article/80p3nyn6.