Одни дроби вида 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
Примеры
Ввод:
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.
Ввод:
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. Следуйте условию и ограничениям выше.