Подразделы

Другие разделы

Дата и время

09/04/2025 16:08:43

Авторизация

Зарегистрироваться
Восстановить пароль

962. Цепные дроби

Цепные дроби Рис. 1

Цепные дроби

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Простая цепная дробь имеет вид

где

$a_i$ – целые числа. Такую цепную дробь можно записать в виде

$[a_1,\ a_2,\ a_3,\ …,\ a_n]$ . Нетрудно показать, что любое рациональное число

$p/q$ , где

$p$ ,

$q$ – целые числа и

$p\ >\ q\ >\ 0$ может быть единственным образом представлено цепной дробью

$[a_1,\ a_2,\ …,\ a_{n-1},1]$ , где

$n$ и

$a_i$ – натуральные числа.

Напишите программу, которая для заданного рационального числа находит и печатает простую цепную дробь.

Ввод

Входной файл содержит два целых чисел

$p$ и

$q$ (

$10^18\ >\ p\ >\ q\ >\ 0$ ).

Вывод

Запишите в выходной файл результат как показано в примере. Цепная дробь должна быть напечатана с соблюдением следующих правил:

Горизонтальные линии состоят из символов "-" (минус);
Ширина каждой горизонтальной линии в точности равна ширине знаменателя;
Пробелы изображаются символами "." (точка);
Единицы в числителях должны выравниваться по центру горизонтальной линии, то есть, слева и справа от единицы должно быть одинаковое количество пробелов, если это возможно. В противном случае один дополнительный пробел должен быть добавлен справа.

Пример ввода 1

75 34

Пример вывода 1

..........1......
2.+.-------------
............1....
....4.+.---------
..............1..
........1.+.-----
................1
............5.+.-
................1

Пример ввода 2

65 60

Пример вывода 2

......1...
1.+.------
.........1
....11.+.-
.........1

Источник: Весенний турнир имени Мартовского Зайца, 2007