Stern-Brocot Tree (SBT) 上で考えると，以下のような問題とみなせます．

条件 \(\frac{A}{B}\lt\frac{p}{q}\lt\frac{C}{D}\) を満たす \(p/q\) のうち，SBT で最も浅い位置にあるもの（一意に存在する）を求めよ．

解法を 2 つ紹介します．

解法1. 愚直に SBT を降りる

SBT の根から始めて \(\frac{A}{B}\) 以下なら右へ，\(\frac{C}{D}\) 以上なら左へ降りることを繰り返せば答えが得られます．

上の内容は，128 bit 整数型などを用いればそのまま実装できます：実装例 (C++)．

• 128 bit での乗除算をテストケースあたり \(O(\log\max(A,B,C,D))\) 回行うので，言語および実装によっては TLE の可能性があります．

また与えられた有理数に対応する SBT 上の頂点を求めるときと同様に考えると，例えば以下のようにすれば 64 bit 整数の範囲で計算できます．

• 根から始めて以下を繰り返す．
  • \(n\coloneqq\lfloor\frac{A}{B}\rfloor\) とする．
  • SBT 上で初回は右，それ以降は直前と違う方向に \(n\) 個降りる．
  • \((A,C)\leftarrow(A-Bn,C-Dn)\) とする．
  • \(1\lt\frac{C}{D}\) なら今いる頂点を解として終了．
  • \((A,B,C,D)\leftarrow(D,C,B,A)\) とする．

実装例 (Python)

なおこの解法は公式解説の解法と本質的に同じですが，非再帰になっています．

解法2. 閉区間に帰着

Stern–Brocot Tree - Library Checker における RANGE, LCA を用いることを考えます．

条件が等号付き \(\frac{A}{B}\leq\frac{p}{q}\leq\frac{C}{D}\) の場合は単に LCA を求めればよいことに着目し，等号付きの条件への帰着を考えます．

\(\frac{A}{B}\lt\frac{A+C}{B+D}\lt\frac{C}{D}\) より解の上界として \(B+D\) が取れます．

開区間 \((x,y)\) に含まれる分母が \(m\coloneqq B+D\) 以下の既約分数で最小のものを \(u\)，最大のものを \(v\) とし，有理数 \(s,t\) を \(x\lt s\leq u,v\leq t\lt y\) を満たすようにとると，\(s,t\) の LCA を求めれば元の問題は解けます．

\(s\) は例えば \(x\) の右の子から始め，分母が \(m\) を超えるまで左へ降りることを繰り返せば得られます．\(t\) も同様です．

実装例 (Python)

注意点として 64 bit 整数を用いて上記をそのまま実装すると，以下のようなケースで \(s,t\) を求めるときにオーバーフローの可能性があります．

1
1000000000000000000 999999999999999999 1000000000000000000 999999999

開区間が整数を含む場合を別途処理し，平行移動して \(\frac{C}{D}\lt 1\) としておけば回避できます．