超实用!Stern-Brocot tree总结奉上

关于Stern-Brocot tree网上的资料较少,能够找到的资源有Wikipedia以及《具体数学》上的介绍,这里大概总结一下这个树形结构的性质。

Stern-Brocot tree:

Stern-Brocot tree构成了一个无限的二叉排序树,可以将所有的正有理数从小到大列举出来。

构造方法可以理解为:先在左边写上\(\frac{0}{1}\),右边写上\(\frac{1}{0}\),代表零和正无穷,然后分子、分母分别相加,得到\(\frac{1}{1}\),写在中间,之后每次把当前层复制到下一层,然后对于下一层相邻两个有理数之间还是分子分母分别相加,得到新的有理数,写在两者中间,重复这个操作就可以无限的写下去,进而得到所有的有理数。树形结构的获得见上图。

记树中的一个节点\(\frac{y}{x}\),它是由\(\frac{L_m}{L_n},\frac{R_m}{R_n}\)这两个数产生的,那么可以发现:

1.\(\frac{L_m}{L_n}\)是位于左上方且离它最近的祖先,\(\frac{R_m}{R_n}\)是位于右上方且离它最近的祖先。

2.\(gcd(x,y)=1\)。

3.\(R_mL_n-L_mR_n=1\)。

4.以\(\frac{y}{x}\)为根的子树中的所有数都落在区间\((\frac{L_m}{L_n},\frac{R_m}{R_n})\)中

找一个数\(\frac{b}{a}\)在树中的位置可以通过在树上二分,但如果一步一步走的话,时间复杂度关于a,b是线性的,比如找\(\frac{1}{10^9}\)。但是可以证明,在树上“拐弯”的次数是\(O(log)\)的(证明和斐波那契有关,暂时还没想好怎么证),这样每次直走的步数我们可以列不等式\(O(1)\)求出,拐弯的过程递归下去就好了。

题目列表:

1.2017 CCPC 哈尔滨 Cow`s Segment

题意:给两个高精度浮点数\(a,b\),求最小的正整数\(x\)使得区间\([ax,bx)\)包含整数(注,原题面有误,真实的数据是左闭右开的)。

思路:设\(ax\le y<bx\),即\(a\le \frac{y}{x}<b\),就按上面说的,在Stern-Brocot tree上二分,直到找到第一个符合条件的点,同时就是x的最小值。

(Java写起来太长了

 

2.Petrozavodsk Winter-2018. AtCoder Contest C Construct Point

题意:二维平面上给整点三角形的三个顶点坐标,判断三角形内部(不含边界)是否存在整点,如果有输出任意一个。

思路:先考虑这么一个子问题,在直线\(y=\frac{b}{a}x\)和\(y=\frac{d}{c}x\)之间找一个整点,范围\(0<x\le D\),那么还是\(\frac{b}{a}x < y<\frac{d}{c}x\),得到\(\frac{b}{a}<\frac{y}{x}<\frac{d}{c}\),找到最小的x和D比较即可。对于任意三角形的话,通过分割,平移,对称的变换就能规约成上述子问题啦。

代码略。