ACM►学习笔记►数学

两分数间分母最小的分数

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

这个问题很显然，我们应该转移到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;
    }
}