　以下の補題を示す．$(a_0, b_0)$ を初期値として操作をおこない， $N$ 回目の更新の直後に操作が停止したものとする．また，
$$
\frac{\max \\{a_{n}, b_{n}\\}}{\min \\{a_{n}, b_{n}\\}}=k_{n}
$$
と表記することにする．
---
**補題 1.** $0$ 以上 $N-1$ 以下の任意の整数 $n$ に対し，以下が成立する． （ただし，$a_{N} = b_{N} =1$ となる場合は考えないものとする．）
$$
a_{n} \gt b_{n} \Longleftrightarrow a_{n+1} \lt b_{n+1}
$$
<details>
<summary>証明<\/summary>
　$a_{n} \gt b_{n}$ かつ $a_{n+1} \gt b_{n+1}$ とすると，
$$
a_{n} a_{n+1} -b_{n} b_{n+1} \gt b_{n} (a_{n+1}-b_{n+1})\gt 1
$$
となり，$a_{n} a_{n+1} -b_{n} b_{n+1}=1$ に矛盾する．$a_{n} \lt b_{n}$ かつ $a_{n+1} \lt b_{n+1}$ と仮定した場合でも同様である．
<\/details>

**補題 2.** $0$ 以上 $N$ 以下の任意の整数 $n$ に対し，以下が成立する．
$$
\lfloor k_{0} \rfloor \leq k_{n} \leq \lfloor k_{0} \rfloor +1
$$
なお，いずれかの不等式の等号が成立するのは，$n=N$ のときのみである．

<details>
<summary>証明<\/summary>
　数学的帰納法で示す．$n=0$ は明らか．以下，ある整数 $n$ で補題 2 の成立を仮定し，$n+1$ でも補題 2 が成立することを，背理法を用いて示す．$a_{n} \gt b_{n}$ のとき
$$
a_{n} a_{n+1} - b_{n} b_{n+1} =1 \Longrightarrow k_{n+1} = \frac{a_{n} a_{n+1} -1}{a_{n+1}b_{n}} \lt k_{n} \leq  \lfloor k_{0} \rfloor +1.
$$
ここで $k_{n+1} \lt \lfloor k_{0} \rfloor$ を仮定すると，
$$
1=a_{n} a_{n+1} - b_{n} b_{n+1}= a_{n+1} ( a_{n} -k_{n+1} b_{n} ) \gt a_{n+1}(a_{n} - \lfloor k_{0} \rfloor b_{n})  \geq 1
$$
となり矛盾する．以上より $\lfloor k_{0} \rfloor \leq k_{n} \leq \lfloor k_{0} \rfloor +1$ である．$a_{n} \lt b_{n}$ のときも同様である．
<\/details>

**補題 3.** $a_{n}, b_{n}, a_{n+1}, b_{n+1}$ がいずれも $3$ 以上の整数であるとき，以下が成立する． 
$$
\begin{aligned}
\lfloor k_{0} \rfloor \lt k_{n} \lt \lfloor k_{0} \rfloor + \frac{1}{2}
& \Longleftrightarrow 
\lfloor k_{0} \rfloor \lt k_{n+1} \lt \lfloor k_{0} \rfloor + \frac{1}{2}
\\\\
\lfloor k_{0} \rfloor + \frac{1}{2} \lt k_{n} \lt \lfloor k_{0} \rfloor +1 & \Longleftrightarrow 
\lfloor k_{0} \rfloor + \frac{1}{2} \lt k_{n+1} \lt \lfloor k_{0} \rfloor +1
\end{aligned}
$$

<details>
<summary>証明<\/summary>
　はじめに，$\Longrightarrow$ について示す．\
　$a_{n} \gt b_{n} \geq 3$ とし，$a_{n}= \lfloor k_{0} \rfloor  b_{n}+r_{n}$ とおく．補題 2 より $\lfloor k_{0} \rfloor = \lfloor k_{n} \rfloor $ であるから，$r_{n}$ は $1$ 以上 $b_{n}$ 未満の整数となる．また，$a_{n}$ と $b_{n}$ が互いに素であるから，$b_{n}$ の偶奇によらず $r_{n}={b_{n}}\/{2}$ になりえないことに注意してほしい．

 - $k_{n}  \lt \lfloor k_{0} \rfloor+1\/2$ のとき，$r_{n}\lt b_{n}\/2$ である．補題 2 と合わせて以下の不等式が成り立つ．
$$
\lfloor k_{0} \rfloor +\frac{1}{2} \gt k_{n} = \frac{b_n b_{n+1}+1}{b_{n} a_{n+1}} \gt  k_{n+1} 
$$

 - $k_{n} \gt \lfloor k_{0} \rfloor +1\/2 $ のとき，$r_n\gt b_{n}\/2$ である．ここで $k_{n+1} \leq \lfloor k_{0} \rfloor + 1\/2$ を仮定すると，
$$
1=a_n a_{n+1} - b_n b_{n+1}= a_{n+1} (a_n - k_{n+1} b_n ) \geq a_{n+1}\Bigl(r_n - \frac{b_n}{2}\Bigl) \geq \frac{a_{n+1}}{2}  \gt 1
$$
となり矛盾する．補題 2 と合わせて所望の結果を得る．

　$b_n \gt a_n \geq 3$ のときも同様に示すことができる．\
　さらに，$\Longleftarrow$ についても同様の示し方ができる．
<\/details>

**補題 4 .** 以下の一次不定方程式
$$
\begin{aligned}
(2 \lfloor k_{0} \rfloor +1) x - 2y = 1 \\\\
2x - (2 \lfloor k_{0} \rfloor +1) y = 1 \\\\
x - \lfloor k_{0} \rfloor y = 1 \\\\
(\lfloor k_{0} \rfloor +1)x - y = 1 
\end{aligned}
$$

の正の整数の組の一般解は，ある非負整数 $t$ を用いることにより，上から順に次のように表される．
$$
(x,y) = ( 2t+1, 2 \lfloor k_{0} \rfloor t + t +\lfloor k_{0} \rfloor ) \tag{1}
$$
$$
(x,y) = (2 \lfloor k_{0} \rfloor t + t +\lfloor k_{0} \rfloor +1, 2t+1 ) \tag{2}
$$
$$
(x,y) = (\lfloor k_{0} \rfloor t + \lfloor k_{0} \rfloor+1, t+1)\tag{3}
$$
$$
(x,y) = ( t+1, \lfloor k_{0} \rfloor t  + \lfloor k_{0} \rfloor + t ) \tag{4}
$$
<details>
<summary>証明<\/summary>
　実際に計算することによって示される．\
　ここで，$\min\\{x,y\\} \geq 3$ の場合，$(1), (3)$ の解の比は $\lfloor k_{0} \rfloor + \frac{1}{2}$ より小さく，$(2), (4)$ の解の比は $\lfloor k_{0} \rfloor + \frac{1}{2}$ より大きくなっていることに留意してほしい．
<\/details>

**補題 5 .** $\min\\{a_{0}, b_{0}\\} \geq 3$ のとき，以下が成立する．
$$
\begin{aligned}
\lfloor k_{0} \rfloor \lt k_{0} \lt \lfloor k_{0} \rfloor+\frac{1}{2} 
& \Longleftrightarrow (a_{N}, b_{N})=(1, \lfloor k_{0} \rfloor)\\\\
\lfloor k_{0} \rfloor+\frac{1}{2} \lt k_0 \lt \lfloor k_{0} \rfloor +1 
& \Longleftrightarrow (a_{N}, b_{N})=(\lfloor k_{0} \rfloor+1,1)
\end{aligned}
$$
<details>
<summary>証明<\/summary>
はじめに $\Longleftarrow$ について示す．

 - $\min \\{a_{N-1}, b_{N-1}\\} \geq 3$ の場合．
    - $(a_{N}, b_{N}) = (1, \lfloor k_{0} \rfloor)$ のとき．
$(x,y)=(a_{N-1}, b_{N-1})$ は $x-\lfloor k_{0} \rfloor y=1$ の整数解の $1$ つである．補題 4 より $k_{N-1} \lt \lfloor k_{0} \rfloor +\frac{1}{2}$ だから，補題 3 より $\lfloor k_{0} \rfloor \lt k_{0} \lt \lfloor k_{0} \rfloor+\frac{1}{2}$ が従う．
    - $(a_{N}, b_{N})=( \lfloor k_{0} \rfloor +1, 1)$ のとき．
$(x,y)=(a_{N-1}, b_{N-1})$ は $(\lfloor k_{0} \rfloor +1)x - y = 1$ の整数解の $1$ つである．補題 4 より $k_{N-1} \gt \lfloor k_{0} \rfloor +\frac{1}{2}$ だから，補題 3 より $\lfloor k_{0} \rfloor+\frac{1}{2} \lt k_0 \lt \lfloor k_{0} \rfloor +1$ が従う．

 - $\min \\{a_{N-1}, b_{N-1}\\} =2$ の場合．補題 2 をふまえれば，$\max \\{a_{N-1}, b_{N-1}\\} = 2 \lfloor k_{0} \rfloor+1$ である．
    - $(a_{N}, b_{N})=(1, \lfloor k_{0} \rfloor)$ のとき．
 $(a_{N-1}, b_{N-1})=(2 \lfloor k_{0} \rfloor+1, 2)$ である．また，$(x,y)=(a_{N-2}, b_{N-2})$ は $(2 \lfloor k_{0} \rfloor +1) x - 2y = 1$ の整数解の $1$ つである．補題 4 より $k_{N-2} \lt \lfloor k_{0} \rfloor + \frac{1}{2}$ となり，補題 3 より $\lfloor k_{0} \rfloor \lt k_{0} \lt \lfloor k_{0} \rfloor+\frac{1}{2}$ が従う．
    - $(a_{N}, b_{N})=(\lfloor k_{0} \rfloor +1, 1)$ のとき．
 $(a_{N-1}, b_{N-1})=(2, 2  \lfloor k_{0} \rfloor +1)$ である．また，$(x,y)=(a_{N-2}, b_{N-2})$ は $2x - (2 \lfloor k_{0} \rfloor +1) y = 1$ の整数解の $1$ つである．補題 4 より $k_{N-2} \gt \lfloor k_{0} \rfloor + \frac{1}{2}$ となり，補題 3 より $\lfloor k_{0} \rfloor+\frac{1}{2} \lt k_0 \lt \lfloor k_{0} \rfloor +1$ が従う．

　$\Longrightarrow$ については，対偶をとることによって示される．
<\/details>

---
　$x=1$ の場合，$N=0$ であるから，更新が停止したとき $ (2^{25}, 1), (1, 2^{25})$ が残る．\
　$x \geq 3$ の場合を考えよう．補題5より，$x \in S \setminus \\{1\\}$ がある正整数 $m$ によって，$m \lt 2^{26}\/x \lt m+1$ と評価されているとき，

 - $m$ が偶数ならば，正整数の組 $(2^{25}, x), (x, 2^{25})$ は操作によって $(1, m\/2)$ になる．
 - $m$ が奇数ならば，正整数の組 $(2^{25}, x), (x, 2^{25})$ は操作によって $((m+1)\/2, 1)$ になる．

ことがわかる．したがって，今回の問題は上記の不等式を満たす $x \in S$ が存在するような整数 $m$ が何種類存在するかということに帰着される．これは $\lfloor {2^{26}}\/{x}  \rfloor$ が異なる整数を何種類もつかという問題そのものである．\
　$n = 2, 3, \cdots , 2^{24}$ に対し，数列$\\{p_n\\}$ を次のように定める．
$$
p_n = \frac {2^{26}}{2n-1}
$$
また，$\\{p_n\\}$ が単調減少であることを踏まえ， $2 \leq n \leq 2^{24}-1$ に対し，$\\{d_n\\}$ を以下のように定める．
$$
d_{n} = p_{n} - p_{n+1} = \frac{2^{27}}{(2n-1)(2n+1)}
$$

 - $2 \leq n \leq 5792$ のとき\
$d_{n} \gt 1$ であるから，$\lfloor p_{n} \rfloor$ と $\lfloor p_{n+1} \rfloor$ は相異なる．

 - $5793 \leq n \leq 2^{24}-1$のとき\
$d_n \lt 1$ であることから， $\lfloor p_{n} \rfloor$ は $\lfloor p_{2^{24} } \rfloor =2$ から $\lfloor p_{5793} \rfloor = 5792$ までのすべての値をとりうる．

　以上より，求める答えは $2 + 5791 + 5791= \textbf{11584}$ 種類である．
公式解説
https://onlinemathcontest.com/contests/omc186/editorial/5815
初期値が $(x,2^{25})$ であるようなものの最終的な値は以下のようにして求まる .

---

[Stern-Brocot tree](https:\/\/en.wikipedia.org\/wiki\/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$ を数える問題になる.

以降は公式解説と同じなので省略することにする.
ユーザー解説
https://onlinemathcontest.com/contests/omc186/editorial/5815/320
不変量を作って解く方法を解説する．

**アイディア**

$a_n$と$b_n$の（大きい方）\/（小さい方）の値を$k_n$とする．$k_n$は遷移によってあまり変わらないので，$k_n$を利用して不変量を作るのが良さそうである．そこで小さい数で$k_n$の遷移を観察しよう．例えば
$$(32,5)\to (3,19)\to (13,2)\to (1,6)$$
という遷移の場合，$k_n$は
$$6.4\to 6.33\dots\to 6.5\to 6$$
となり，$6$から$6.5$の間を動く．また
$$(7,32)\to (23,5)\to (2,9)\to (5,1)$$
という遷移の場合，$k_n$は
$$4.57\dots\to 4.6\to 4.5\to 5$$
となり，$4.5$から$5$の間を動く．
このような例から，$k_n$以下の最大の**0.5の倍数**が不変であることが予想できる．ただし一つ目の例の$6.5$は$6.4999\dots$と解釈する（つまり$6.5$より小さいかのように扱う）必要があり，二つ目の例の$5$は$4.9999\dots$と解釈する（つまり$5$より小さいかのように扱う）必要がある．このような発想で不変量を作ると以下のようになる．

なお，ここまでの考察をもとに正しく不変量を予想できれば，それが不変量であることを証明せずとも答えを導くことができる．

**解答**

実数$x$に対し，$x$以下の最大の$0.5$の倍数を$\langle x\rangle$で表すことにする．
定義から$a_n$と$b_n$は常に互いに素であり，したがって$a_n=b_n$となるのは$(a_n,b_n)=(1,1)$の場合のみである．また，$(a_n,b_n)\neq (1,1)$ならば$a_{n-1}-b_{n-1}$と$a_n-b_n$の符号は異なる（公式解説参照）．ここで十分小さい正の実数$\varepsilon$（例えば$\varepsilon=2^{-100000000000}$）を取り，
$$P_n=\begin{cases}\langle k_n-\varepsilon\rangle&(a_n\gt b_n)\\\ \langle k_n+\varepsilon\rangle&(a_n\leq b_n)\end{cases}$$
と定める．ただし$k_n=\max\\{a_n,b_n\\}\/\min\\{a_n,b_n\\}$である．このとき$P_{n-1}=P_n$が成り立つことを示そう．
- $a_{n-1}\gt b_{n-1}$の場合，前述のように$a_n\leq b_n$であり，$(a_{n-1},b_{n-1})$が終状態でないことから$b_{n-1}\geq 2$である．これらと$a_{n-1}a_n-b_{n-1}b_n=1$を合わせると
$$\dfrac{b_n}{a_n}\lt\dfrac{a_{n-1}}{b_{n-1}}\leq\dfrac{b_n+0.5}{a_n}$$
が得られる．したがって$k_n+\varepsilon, k_{n-1}-\varepsilon$はいずれも$\dfrac{b_n}{a_n}\lt x\lt \dfrac{b_n+0.5}{a_n}$の範囲にあるが，この範囲には$\dfrac{0.5}{a_n}$の倍数が存在しないので，特に0.5の倍数は存在しない．よってこれらに対する$\langle{x}\rangle$の値は一致する．
- $a_{n-1}\lt b_{n-1}$の場合，$(a_n,b_n)\neq(1,1)$となるため$a_n\gt b_n$であり，$(a_{n-1},b_{n-1})$が終状態でないことから$a_{n-1}\geq 2$である．これらと$a_{n-1}a_n-b_{n-1}b_n=1$を合わせると
$$\dfrac{a_n-0.5}{b_n}\leq\dfrac{b_{n-1}}{a_{n-1}}\lt\dfrac{a_n}{b_n}$$
が得られる．したがって$k_{n-1}+\varepsilon, k_n-\varepsilon$はいずれも$\dfrac{a_n-0.5}{b_n}\lt x\lt \dfrac{a_n}{b_n}$の範囲にあるが，この範囲には$\dfrac{0.5}{b_n}$の倍数が存在しないので，特に0.5の倍数は存在しない．よってこれらに対する$\langle{x}\rangle$の値は一致する．

以上より$P_n$の値は$n$によらず一定である．終状態$(a_N,b_N)$における値は
$$\begin{aligned}&(a_N,b_N)=(m,1),m\gt1\implies P_N=m-0.5,\\\ &(a_N,b_N)=(1,m),m\geq 1\implies P_N=m\end{aligned}$$
となり全て異なるため，**終状態としてあり得る組の総数は，$P_0$としてあり得る値の総数に等しい**．初期状態$(a_0,b_0)$における値は
$$\begin{aligned}&(a_0,b_0)=(2^{25},1),(1,2^{25})\implies P_0=2^{25}-0.5,2^{25},\\\ &(a_0,b_0)=(2^{25},x),(x,2^{25})\implies P_0=\langle 2^{25}\/x\rangle=\dfrac{1}{2}\lfloor 2^{26}\/x\rfloor\quad(x=3,5,7,\dots,2^{25}-1)\end{aligned}$$
となるため，$x=3,5,7,\dots,2^{25}-1$に対する$\lfloor 2^{26}\/x\rfloor$としてあり得る値の総数に$2$を加えたものが答えである．あとは公式解説と同様である．
不変量を作る
https://onlinemathcontest.com/contests/omc186/editorial/5815/323
　互いに素な $2$ つの正整数の組 $(a_0, b_0)$ について，これを初期値として，ある $2$ つの正整数の組から別のある $2$ つの正整数の組へ更新することを繰り返します．$n$ 回目の更新で得られる正整数の組 $(a_n, b_n)$ は，以下で与えられるものとします： 

 - 方程式 $a_{n-1}x-b_{n-1}y=1$ の正整数解 $(x, y)$ のうち，$x$ が最小のもの．

この更新を，$2$ つの成分のうち少なくとも一方が $1$ に**初めて**なるまで何回か（$0$ 回でもよい）繰り返して，その時点で停止させることを考えます．

---

　いま，$1$ 以上 $2^{25}-1$ 以下の奇数全体からなる集合を $S$ とし，集合 $T$ を
$$
T = \\{ (2^{25}, x) \mid x \in S \\} \cup \\{ (x, 2^{25}) \mid x \in S \\}
$$ 
で定めます．集合 $T$ に含まれるすべての組それぞれに対し，それを初期値として上記の更新が停止したとき，最終的に得られる組としてありうるものは全部でいくつですか？\
　ただし，集合 $T$ に属するすべての組について，有限回で更新が停止することが保証されます．