两分数间分母最小的分数

给你两个分数,让你找一个分数在他们俩之间,要求分母最小,

这个问题很显然,我们应该转移到Stern Brocot Tree上面去做,对于给定的两个分数,我们把他们在树上标记出来,可能他们不在树的同一层,但是我们可以找到一个合适的层数,并且把他们标记在这一层,可能标记后,他们之间没有其他分数,那我们就选择更深的一层,直到他们在同一层,且中间有其他数字。

这时我们来分析答案在哪,首先很容易证明答案就在他们俩之间的那些分数之间,因为这些分数已经满足了值在他们俩之间,对于另一个要求-分母最小,这就要求我们在这些分数中取出一个分母最小的。

有一个很简单的做法可以帮助我们找到答案,那就是,把这些可能的答案全部标记为红色,真正的答案就是这些标记的lca。

当我们发现答案是lca的时候,我们也发现了另一个现象,分子分母具有轮换对称性当分母取到最小值的时候,分子可能有多个解,如果我们选择了最小的分子,我们将得到一个分数 $\frac{a1}{b1}$ 我们发现如果不考虑分母最小,此时的分子也是所有解中最小的分子。

换句话说,在$(\frac{u}{v},\frac{x}{y})$中所有分母最小的分数中选择一个分子最小的分数和$(\frac{u}{v},\frac{x}{y})$中所有分子最小的分数中选择一个分母最小的分数,选出的结果一定是相同的。

于是我们就可以利用此特征来解决上诉问题了,代码如下,若区间包含了一个整数z,那么答案一定是$\frac{z}{1}$,否则我们可以将区间向左移动,理由是,尽管分子变了,但是区间移动不影响分母的大小,再根据分母最小时的分子最小的答案 等于 分子最小时分母最小的答案 即分母能唯一确定分子,通过区间移动后的分母的最小值推出区间移动前的分母最小值,进而推出区间移动前的分子的最小值,我们就能解决这个问题了。
用辗转相除加速。

1
2
3
4
5
6
7
8
void solve(ll u1,ll u2,ll&r1,ll&r2,ll v1,ll v2){ // u1/u2<r1/r2<v1/v2
if((u1+u2-1)/u2<=v1/v2) r1=(u1+u2-1)/u2,r2=1;
else{
ll d=u1/u2; //u1/u2-d<r1/r2-d<v1/v2-d
solve(v2,v1-v2*d,r2,r1,u2,u1-u2*d);
r1+=d*r2;
}
}