Все задачи
Сложно Решено: 0 Процент решений: 0%

Самый длинный период дроби

Найдите d не больше предела, для которого у дроби 1/d самый длинный период в десятичной записи.

Чему вы научитесь

  • Моделировать деление столбиком с помощью остатков
  • Находить повтор с помощью таблицы
  • Вычислять длину цикла по первым позициям

Условие

Одни дроби вида 1/d конечны (1/4 = 0,25), а остальные повторяются бесконечно: у 1/6 = 0,1666... период из 1 цифры, а у 1/7 = 0,142857142857... период из 6 цифр. Среди d = 2, 3, ..., limit найдите такое d, у которого период дроби 1/d самый длинный. Запрограммируйте деление столбиком: цифры начинают повторяться, как только снова появляется уже встречавшийся остаток.

Реализуйте longest_recurring_cycle(limit).

Входные данные

limit: наибольший знаменатель, который нужно проверить.

Выходные данные

Верните d с самым длинным периодом. У конечной дроби длина периода равна 0. Если таких d несколько, верните наименьшее.

Ограничения

2 ≤ limit ≤ 2000

Примеры

Пример 1
Ввод:
limit = 8

Ожидаемый вывод:
expected = 7
Ввод:
long long limit = 8;

Ожидаемый вывод:
long long expected = 7;
Ввод:
long limit = 8;

Ожидаемый вывод:
long expected = 7;

Пояснение

Длины периодов для d от 2 до 8: 0, 1, 0, 0, 1, 6, 0, поэтому ответ 7.

Пример 2
Ввод:
limit = 5

Ожидаемый вывод:
expected = 3
Ввод:
long long limit = 5;

Ожидаемый вывод:
long long expected = 3;
Ввод:
long limit = 5;

Ожидаемый вывод:
long expected = 3;

Пояснение

У 1/3 повторяется одна цифра, а 1/2, 1/4 и 1/5 конечны, поэтому ответ 3.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Каждая новая цифра 1/d получается из остатка, умноженного на 10.

Подсказка 2

Запоминайте шаг, на котором каждый остаток появился впервые.

Подсказка 3

Если остаток стал равен 0, дробь конечна; иначе длина периода равна расстоянию между двумя появлениями одного и того же остатка.

Ожидаемая сложность

время O(limit²), доп. память O(limit)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.