|
Дистанционный практикум по программированию
|
||||||||||
|
|
|||||||||||
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
1728. Цепные дроби
|
| Статистика | Послать на проверку | Задачу добавил debug |
|
Цепная дробь (или непрерывная дробь) – это математическое выражение вида
где a0 – целое число, все остальные элементы ai – положительные целые числа. Для удобства такую дробь можно записать следующим образом: [a0;a1, a2, a3, ...] Бесконечная цепная дробь, в которой определенная последовательность элементов, начиная с некоторого места, периодически повторяется, называется периодической. Если периодическое повторение начинается сразу с элемента a1 (то есть отсутствует предпериод), то такая дробь называется чисто периодической. В данной задаче требуется представить корень квадратный из положительного целого числа N в виде чисто периодической цепной дроби (такое представление всегда возможно и однозначно). Входные данные В единственной строке входных данных записано положительное целое число N, не являющееся полным квадратом (2 ≤ N ≤ 105). Выходные данные Выведите равенство в соответствии с примерами. Длина периода в ответе должна быть минимальной. Примеры Входные данные 2 Выходные данные sqrt(2) = [1; 2] Входные данные 12 Выходные данные sqrt(12) = [3; 2, 6] Входные данные 22 Выходные данные sqrt(22) = [4; 1, 2, 4, 2, 1, 8] Примечание Во втором примере получается следующая чисто периодическая цепная дробь:
|
| Статистика | Послать на проверку | Обсуждение задачи | Автор/источник: |
| Задачи с соревнований и сборов / | Межвузовские олимпиады / | XX межвузовская олимпиада - 2017 / |
| 1727. H - Пирамиды | 1728. | 1729. J - Склад |
| время генерации 0.094 сек. | |
| © Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А. |