双曲线下整点计数——SBT的一点应用

Fatalis_Lights · 2020-09-18 18:31:43 · 个人记录

Part 0. 前言

本篇为笔者学习 DIVCNT1 时留下的一点学习小记，公式之类的笔误可以直接在评论区提出，笔者会尽快修复。

Part 1. 问题的引入

给定双曲线：

求 T_1 下方的整点个数（含经过的点， 1\leq n\leq 2^{63} ）。

• 这便是双曲线下整点计数的最原始的形式了。
• 本题即为 SP26073 。

Part 2. 问题的初步探讨

原式即等价于求：

记原式答案为 T_2(n) ，则有：

至此，我们已经可以在 \Theta(\sqrt{n}) 的 naive 复杂度下解出答案，但显然我们需要更快的做法。

Part 3. Stern-Brocot Tree 和 Farey 序列的引入

Stern-Brocot Tree （以下简称 SBT ）： SBT 是一棵无穷大的完全二叉树，每个节点都代表一个最简分数，且与有理数对应。它满足搜索树的性质，即左子树的所有数都小于根代表的数，右子树的所有数都大于根代表的数。（其它有趣的性质可参见 BiliBili的小视频 ）

抓一张图过来以便于理解：

（当然图中的这棵树只是 SBT 的一部分）

Farey 序列： 将所有分母小于等于 n 的最简真分数从小到大排列，形成的序列即为 Farey 序列。我们称在 Farey 序列中连续出现的分数为 Farey Neighbour 。若 \dfrac{a}{b} 和 \dfrac{c}{d} 为 Farey Neighbour ，且 \dfrac{a}{b}>\dfrac{c}{d}，则有： ad-bc=1 。（证明可食用参考文献）

（图片有点小。。请见谅 >_< ）

如上的科技将会对我们解题有帮助。

Part 4. 问题的深入探讨

回到原题，我们求的即为满足： xy\leq n , y\leq[\sqrt{n}] 且在坐标轴正半轴右上方的整点个数。

贺一著名图片：

• 我们所求的即为粉色区域的整点数（别管坐标轴上的数字）

我们考虑利用 SBT 切割曲线，如下图所示：

我们很容易能统计出红线下方的整点数。

那么怎么搞右边和上面的部分呢？

首先，我们定义一个函数 S(x_0,y_0,a,b,c,d) 。在下图中， P 点的坐标即为 (x_0,y_0) ，过 P 的两条直线 QP,RP 的斜率分别是 -\dfrac{a}{b} 和 -\dfrac{c}{d} ，R,Q 在双曲线上。 曲边三角形 PQR 内的整点个数即为 S(x_0,y_0,a,b,c,d) 。当 \dfrac{a}{b} 和 \dfrac{c}{d} 不是 Farey Neighbour 时，定义 S(x_0,y_0,a,b,c,d)=0 。

所以我们要求的是 S(0,0,1,0,0,1) 。

我们尝试将原来的 xy 坐标系转化为这里的 PR,PQ 轴坐标系。不妨记 PR 为 R 轴，PQ 为 Q 轴。由定义可知：

所以可得：

由 Farey 序列的性质，我们可以知道原坐标系与 QR 坐标系的点一一对应。

所以原来的双曲线 T_2:xy=n 可以被转化为 QR 坐标系中的曲线。那么令：

有：

所以原双曲线 T_2:xy=n 可转化为 QR 坐标系中的曲线：

因为 w_1,w_2,ab,cd\geq 0 ，所以对于任意 u>0 ，有唯一对应的 v 。对于 v>0 ，也有唯一对应的 u 。

设 Q 点在 Q 坐标轴上的坐标轴为 h_1 ， R 点在 R 坐标轴上的坐标轴为 h_2 。所以我们实际在统计下图中绿线和黑线的左下方部分的整点数量。

如果转化后的问题可解决，那么向下递归，即可做出原问题（在较靠近边界的部分可以暴力计算）。

考虑如何计算转化后的问题，找到 QR 坐标系下斜率为 -1 的点 G ，也就是原坐标系中斜率为 -\dfrac{a+c}{b+d} 的曲线，如下图所示：

于是可以找到另两个整点 S,T 满足：

过 S,T 作切线 G 的平行线：

折线 ASTB 下的整点显然能搞，尝试搞剩下的部分。因为蓝线在原坐标系下的斜率为 -\dfrac{a+c}{b+d} 。由 SBT 的性质，可以得出 \dfrac{a+c}{b+d} 和 \dfrac{a}{c},\dfrac{b}{d} 为 Farey Neighbour ，所以我们可以向下迭代计算。

上方的整点数即为 S(X_B,Y_B,a,b,a+c,b+d) ，右边为 S(X_C,Y_C,a,b,a+c,b+d) 。

论文中将本方法的复杂度证明在了 \Theta(n^\frac{1}{3}\log^3n) ，可能能做到 \Theta(n^\frac{1}{3}\log n) 。

• 这种方法的具体的时间复杂度证明请见参考文献。

Part 5. 优化

事实上，如上的反复切割函数并非必要。我们可以直接用 SBT 来拟合原来的曲线，像下面这样：

取一只单调栈，因为曲线逐渐趋缓，斜率始终保持在 [-1,0] ，因此栈中斜率初始化为 (1,0),(1,1) ，按照斜率单调下降存储。由推得的式子，我们从 ([\dfrac{n}{[\sqrt{n}]}],[\sqrt{n}]+1) 出发。

假设我们拟合到了点 A(x,y) ，那么下一次拟合一定在该点的右侧，且不在蓝色区域内。设下一个点为 B(p,q) ，那么由 Pick 定理，贡献就是：

那么怎么确定这个 B(p,q) 呢？

我们可以取栈顶向量，弹出，然后不断加上它，直到差一步走进蓝色区域。记该向量为 right ，记上一次弹的是 left 。用 SBT 合成出和向量 mid 。

如果 mid 走一步没有进蓝色区域，那么把 right 替换为 mid ，重复步骤。如果走一步进了，且 right 小于等于 right 与 mid 的和向量，则可以直接停止。反之则将 left 替换为 mid 。

在 y\leq n^{\frac{1}{3}} 的时候可直接暴力。

可以证明复杂度为 \Theta(n^{\frac{1}{3}}) ，具体证明同见论文。

Part 6. 问题的一点点推广

我们来求一下三维空间中的“双曲线”下整点个数，即：