OMC186(D)

点数: 600

Writer: ojamesi1357

　互いに素な $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$ に属するすべての組について，有限回で更新が停止することが保証されます．