OMC186(D)

初期値が $(x,2^{25})$ であるようなものの最終的な値は以下のようにして求まる .

Stern-Brocot tree 上で $\dfrac{x}{2^{25}}$ の値を持つ頂点から始めて, 以下の操作を分子が $1$ になるまで繰り返す.

• 今いる頂点の親へと進み続ける.ただし,
  • 奇数回目の操作では ,今いる頂点より小さい値の親へ進んだ時点で操作をやめる.
  • 偶数回目の操作では, 今いる頂点より大きい値の親へ進んだ時点で操作をやめる.

操作終了後にいる頂点の値を $\frac{1}{a}$ としたとき, 操作をした回数が奇数回なら $(a,1)$, 偶数回なら$(1,a)$ が最終的な値.

これを用いると, $x\neq 1$ であれば以下が成り立つ.

• $\frac{2}{2a}\lt \frac{x}{2^{25}}\lt \frac{2}{2a+1}$ を満たす正整数 $a$ が存在するなら, $(x,2^{25})$ の最終的な値は $(1,a)$
• $\frac{2}{2a+1}\lt \frac{x}{2^{25}}\lt \frac{2}{2a+2}$ を満たす正整数 $a$ が存在するなら, $(x,2^{25})$ の最終的な値は $(a+1,1)$

ここまでくれば, 上の二式を満たす $x$ が存在するような $a$ を数える問題になる.

以降は公式解説と同じなので省略することにする.