Ланцюгові дроби#1023

Ланцюгові дроби

1 секунда

128 мегабайтів

Дуже легка

Нехай $b_{0}$ b_0, $b_{1}$ b_1, $b_{2}$ b_2, $\dots$ , $b_{n}$ b_n — деякі цілі числа, причому $b_{k} > 0$ b_k > 0 для $k > 0$ k > 0. Ланцюговий дріб порядку $n$ з коефіцієнтами $b_{1}$ b_1, $b_{2}$ b_2, $\dots$ , $b_{n}$ b_n і початковим цілим $b_{0}$ b_0 визначається наступним виразом:

b_{0} + \frac{1}{b _{1} + \frac{1}{b _{2} + \frac{1}{⋱ + \frac{1}{b _{n}}}}}

b_0 + \cfrac{1}{b_1 + \cfrac{1}{b_2 + \cfrac{1}{\ddots + \cfrac{1}{b_n}}}}

Цей вираз може бути записаний у вигляді $[b_{0}; b_{1}, \dots, b_{n}]$ [b_0; b_1, \ldots, b_n].

Наприклад, ланцюговий дріб порядку $n = 3$ n=3 з числами $[2; 3, 1, 4]$ [2;3,1,4] еквівалентний наступному виразу:

2 + \frac{1}{3 + \frac{1}{1 + \frac{1}{4}}}

2 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{4}}}

Напишіть програму, що знаходить розклад даного раціонального числа в ланцюговий дріб. Для забезпечення унікальності потрібно, щоб $b_{n} > 1$ b_n > 1.

Вхідні дані

Вхідні дані складаються з невизначеної кількості раціональних чисел. Кожне раціональне число задано у вигляді дробу: чисельник і знаменник.

Вихідні дані

Для кожного раціонального числа в окремому рядку виведіть його подання у вигляді ланцюгового дробу.

Приклади

Приклад 1

Loading

b_{0}

b_{1}

b_{2}

b_{n}

b_{k} > 0

k > 0

b_{1}

b_{2}

b_{n}

b_{0}

b_{0} + \frac{1}{b _{1} + \frac{1}{b _{2} + \frac{1}{⋱ + \frac{1}{b _{n}}}}}

[b_{0}; b_{1}, \dots, b_{n}]

n = 3

[2; 3, 1, 4]

2 + \frac{1}{3 + \frac{1}{1 + \frac{1}{4}}}

b_{n} > 1