У нас на тренировке была такая задача: даны расстояния между листьями дерева, требуется восстановить дерево. Количество листьев до 200.
Ещё одна задача у нас была с того же контеста, называется Fibonacci Period, дано число r, числа фибоначчи вычисляются по модулю r. Требуется найти период последовательности. r до 10^9.
Подскажите как можно решить эти задачи. По второй получилось только зависимость от разложения числа на простые, но это ничего не дает, так как для простых ответы тоже не известно как получить.
По второй задаче:
Период чисел Фибоначчи по модулю натурального числа n называется периодом Писано (англ.) и обозначается π(n). Периоды Писано π(n) образуют последовательность:
1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … (последовательность A001175 в OEIS)
Wikipedia
А ты был на последних петрозаводских сборах? :)
Там 1 февраля был контест, после которого на разборе рассказывали, как искать такой период.
В энциклопедии четких формул или алгоритмов я не нашел, но наткнулся на pdf-ку. Возможно она тебе сможет помочь %)
http://www.uni-math.gwdg.de/tschinkel/gauss/Fibon.pdf