Assume two integers $a$ and $b$ ($a > b1 \le b < a$) that form an ordered integer pair $(a, b)$. We can perform a **Euclidean division** on it, which will make it $(b, a \bmod b)$. If we keep performing this division, then $b$ will eventually be $0$. We define the number of Euclidean divisions needed to make $b$ equal $0$ as $k$.↵
↵
Example: $(19, 8)$ → $(8, 3)$ → $(3, 2)$ → $(2, 1)$ → $(1, 0)$. We perform $4$ divisions until $b$ equals $0$, so $k = 4$.↵
↵
With the value of $k$ specified ($1 \le k \le 10^9$), how to find any ordered integer pair $(a, b)$ ($1 \le b < a \le 10^{18}$) that needs exactly $k$ Euclidean division to make $b$ equal $0$? If there does not exist such a pair, report it.↵
↵
---↵
↵
I am also curious about one question: it is all known that the Euclidean algorithm is fast, but the speed of the algorithm is determined by $k$, so may $k$ be infinitely large?
↵
Example: $(19, 8)$ → $(8, 3)$ → $(3, 2)$ → $(2, 1)$ → $(1, 0)$. We perform $4$ divisions until $b$ equals $0$, so $k = 4$.↵
↵
With the value of $k$ specified ($1 \le k \le 10^9$), how to find any ordered integer pair $(a, b)$ ($1 \le b < a \le 10^{18}$) that needs exactly $k$ Euclidean division to make $b$ equal $0$? If there does not exist such a pair, report it.↵
↵
---↵
↵
I am also curious about one question: it is all known that the Euclidean algorithm is fast, but the speed of the algorithm is determined by $k$, so may $k$ be infinitely large?
