Блог пользователя Jughead

Автор Jughead, 14 лет назад, По-русски
У нас на тренировке была такая задача: даны расстояния между листьями дерева, требуется восстановить дерево. Количество листьев до 200.

Ещё одна задача у нас была с того же контеста, называется Fibonacci Period, дано число r, числа фибоначчи вычисляются по модулю r. Требуется найти период последовательности. r до 10^9.

Подскажите как можно решить эти задачи. По второй получилось только зависимость от разложения числа на простые, но это ничего не дает, так как для простых ответы тоже не известно как получить.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
Восстановление: это известная задача. Нужно делать так: возьмем максимальное расстояние из этой таблицы, и между двумя этими вершинами добавим нужное количество левых вершин. А дальше будем брать по одной вершине и привешивать к уже построенному дереву так, чтобы длины путей совпали с данными. Детали и реализацию додумай)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

По второй задаче:

Период чисел Фибоначчи по модулю натурального числа n называется периодом Писано (англ.) и обозначается π(n). Периоды Писано π(n) образуют последовательность:
1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … (последовательность A001175 в OEIS)

Wikipedia

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я это уже читал. Мне это никак не помогло, r до миллиарда
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А ты был на последних петрозаводских сборах? :)

      Там 1 февраля был контест, после которого на разборе рассказывали, как искать такой период.

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В английской Википедии вроде бы написано, как вычислять. Для простого можно воспользоваться формулой, которая выражает числа Фибоначчи через золотые сечения (потому что можно извлечь корень по простому модулю).
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      В энциклопедии четких формул или алгоритмов я не нашел, но наткнулся на pdf-ку. Возможно она тебе сможет помочь %)

      http://www.uni-math.gwdg.de/tschinkel/gauss/Fibon.pdf