Задача
Единичная дробь имеет 1 в числителе. Десятичные представления единичных дробей со знаменателями от 2 до 10 даны ниже:
1/2=0.5
1/3=0.(3)
1/4=0.25
1/5=0.2
1/6=0.1(6)
1/7=0.(142857)
1/8=0.125
1/9=0.(1)
1/10=0.1
Где 0.1(6) значит 0.166666..., и имеет повторяющуюся последовательность из одной цифры. Заметим, что 1/7 имеет повторяющуюся последовательность из 6 цифр.
Найдите значение d < 1000, для которого 1/d в десятичном виде содержит самую длинную повторяющуюся последовательность цифр.
Решение (неправильное)
Лобовым методом может показаться следующее: разделить 1 на какое-то число, перевести результат в строку и в этой строке искать повторяющуюся подстроку. Но этот метод и сложный, и ненадёжный ввиду неточности компьютерного представления вещественных чисел.
Кроме того, он в принципе не может дать правильный ответ, так как мы никогда не докажем, что найденная повторяющаяся последовательность будет повторяться вечно, а не изменится в какой-то момент.
Решение (правильное)
Будем использовать обычное деление в столбик по школьным правилам. При делении образуется остаток, который далее тоже делится, снова образуется остаток и т.д.
Легко заметить, что если при делении образовался тот же самый остаток, который раньше уже был, значит деление зациклилось. Дальше всё повторится. Поэтому количество итераций, совершённое до этого момента, является длиной цикла.
Чтобы запоминать остатки, которые уже были, я использую кеш-массив mods. Так как по условию задачи делитель не больше 1000, то остаток от деления тоже не может быть больше 1000, и значит размер кеша равен 1000.
Дополнение (см. комменты): Если встречено число с нецикличной дробной частью, счётчик обнуляется.
В качестве небольшой, практически бесполезной оптимизации я начинаю перебор делителей не с 1, а с 7 (потому что 1..6 заведомо не то, что нужно), а делимое равно не 1, а 10 (потому что всё равно будет умножаться на 10 в процессе деления).
Ссылка на онлайн-компилятор языка C с текстом программы
Ещё дополнение: как подсказал Алексей Д., у меня нецикличная часть числа считается как часть цикла. Чтобы этого не случилось, в кеше для остатка я теперь сохраняю значение счётчика, которое предшествовало этому остатку. А в финале это значение вычитается из счётчика. Заодно я переписал код более компактно. И развернул цикл перебора от большего числа к меньшему (пока делитель больше найденного максимального цикла, т.к. длина цикла не может быть больше делителя). И кеш обнуляется не полностью, а только по размеру делителя.
Ссылка на онлайн-компилятор языка C с текстом программы
Подборка всех задач: