有理数の探し方

この記事は Competitive Programming (2) Advent Calendar 2018 - Adventar の 12/11 分です(の予定でした)

連分数展開・Stern–Brocot tree には様々な面白い構造があり、たまにプログラミングコンテストでも出題される割にあまり知らなかった(かつ日本語の記事もあまり見たことがない)ので、紹介していきます。
(Farey 数列という概念も聞いたことがあるかもしれませんが、 Stern-Brocot tree に似たものです)

簡単のため、以下では基本的に非負の有理数を扱います。

Stern–Brocot tree

唐突ですが、Stern–Brocot treeとは以下のような木を指します (from wikipedia)

まず作り方がイメージしやすい方 (この方法はこの図のイメージと少し違いますが)

初め端に $\frac{0}{1}$ と $\frac{1}{0}$ が書かれています。(0以上の有理数からなる区間を表しています)

ここから、以下の操作を繰り返して数列を作ります。

数列で隣り合う全ての有理数の組 $p=\frac{a}{b}$ と $q=\frac{c}{d}$ の間に $\frac{a+c}{b+d}$ を書く。

$\frac{a}{b} < \frac{c}{d}$ のとき明らかに $\frac{a}{b} < \frac{a+c}{b+d} < \frac{c}{d}$ なので、この列は常に(通常の順序で)昇順となっています。( $\frac{a}{b}$ と $\frac{c}{d}$ が隣り合う時、 $ad-bc=-1$ という性質も保存されます)

各頂点が区間を持っており、ある区間を分割して出来る2つの区間が子となった2分木のようなものをイメージすると良いです。

この図から、分母が小さい方から有理数が列挙されていく様子を感じてもらえると思います。

次に詳しくこの木の性質を見る前に、この木と深い関わりのある連分数展開を紹介します。

連分数展開

ここではsimpleな表現のみを考えます。(以下のように、各部分の分子に1しか使えないもののことです)

有理数 x が連分数展開として $\displaystyle a_0 + \frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3...}}}$ と表されるとき $[a_0;a_1,a_2,a_3...$ ] と表記します。

例えば、 $\displaystyle \frac{13}{8}=1+\frac{1}{\frac{8}{5}}=1+\frac{1}{1+\frac{3}{5}}=1+\frac{1}{1+\frac{1}{1+\frac{1}{\frac{3}{2}}}}=1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{2}}}}$ なので、 $\frac{13}{8}=[1;1,1,1,2$ ] です

この連分数の作り方は Euclid の互除法に似た操作となっています。各stepで、 $\frac{p}{q} (p < q)$ を表したいとして、 $\frac{1}{\frac{q}{p}}=\frac{1}{k+\frac{r}{p}}$ (ただし、 $q=pk+r, 0 \leq r < p)$ ) と表せます。

有理数 $\frac{p}{q}$ を連分数展開して $[a_0;a_1,a_2,...,a_k$ ]となったとします。(k : 非負整数, a_0 : 非負整数, a_1, .. : 正の整数)
$ak=1$ のとき、 $[a_0;a_1,a_2,...,a_{k-1}+1$ ] $=[a_0;a_1,a_2,...,a_{k-1},1$ ]ですが、最後が1であることを許さなければ一意に表せます。
(雑ですが、 $\frac{1}{a_i+hoge}$ は正かつ1以下(1となるのは、hogeが無かつa_i=1の時だけ)であるため、毎回整数部分を入れていくしかないので)

まずこの表現の場合、根は[1]です。

そして、 $[a_0;a_1,a_2,...,a_k$ ] ( $=[a_0;a_1,a_2,...,a_k-1,1$ )]の子は、Stern–Brocot treeにおいて $[a_0;a_1,a_2,...,a_k+1$ ]と $[a_0;a_1,a_2,...,a_k-1,2$ }です。

小さい方を左の子にするのですが、これはその数列の長さの偶奇によって変わって、奇数の時は末尾を+1したものの方が大きく、偶数の時はその逆です。

逆に、この頂点の親はakから1を引いたもの(akが1になったら撤去してa_{k-1}に1を足す)ことによって得られます。

(連分数展開をexplicitな展開を書く)

Stern-Brocot tree には綺麗な性質があって、

二分探索木を成す
全ての既約な有理数が1度ずつ現れる

ある頂点の左子孫は全て自分より小さく、右の子孫は全て自分より大きいという性質を満たします。これも深さの偶によりますが、連分数展開で今見ているところ以降を操作すると、右下の部分が変わるだけで

これまた雑ですが、全部が網羅されていそうなことの雑な説明です。

まず深さdには全て異なる2^d 個の頂点があります。

$a_0+a_1+...+a_k$ を観察すると、深さdにある頂点ではこの和がd+1となっていることがわかります。

先頭のみ0が許される & (先頭でない)末尾は1が許されないような和が d+1 の個数を考えます。

d=0の時は[1]のみなので良いです。それ以外の時、oがd+1個あって、末尾と、末尾の1つ手前以外に仕切りを入れると列になるのでこれは 2^d 通りです。

導入が複雑(雑)でしたがこういった性質を利用すると、有理数で近似・有理数の数当てゲーム(例えば整数であれば普通の2分探索で解ける) などができます。

(近似は結構複雑なのでそのうち追記したいですが、気になる人はwikipediaのcontinued fractionを見てください)

例題

XVIII Open Cup named after E.V. Pankratiev. Grand Prix of SPb
E. Decimal Form

$0 \leq a < b \leq 10^9$ なる整数a,bを用いてa/bを計算したものを小数点以下18桁にしたものが10^4個まで与えられるので、それぞれa,bを答えてください

Stern-Brocot treeの上で探索したいのですが、実は下る向きを変える(左の次は右、右の次は左)とすると分母がだいたい倍になるので O(log max) 回しか方向転換せず、それぞれでは doubling してまっすぐ下りることで解けます。別の解法としては、小数点以下18桁の x が与えられるは a/b が[x-10^-19, x+10^-19) に入るということで、この両端を連分数展開すると近似の問題として解くこともできます。

JOI春合宿 2008 day3 Fraction

$1 \leq a < b \leq M$ を満たす既約分数a/bのうち小さい方からk番目を求めよ。 $M \leq 30000, k \leq 200000$