Остаток от деления чисел Фибоначчи

Как решить? Понятное дело, что никаких лет мне не хватит, чтобы вычислить максимальное n. Тут какая-то хитрость должна быть. Ткните носом, куда читать?

Тебе не нужно вычислять само число Фибоначчи, тебе достаточно вычислить отстаток от его деления на m.

Как мне вычислить остаток от деления одного числа Фибоначчи на второе не вычисляя самого числа Фибоначчи?

Так-так, тебе надо вычислить fib(n)%m или fib(n)%fib(m)?

А не мог бы ты объяснить, зачем тебе это понадобилось? Экзамен какой-то что-ли?

Задача олимпиадная же.

Ох уж. Ошибся. Вы правы. Мне надо fib(n)%m.

inline верно заметил.

Остатки от деления чисел Фибоначчи при n > 2 — это периодическая последовательность. Наверное, нужно плясать от этого.

Остатки от деления чисел Фибоначчи

И не только фибоначчи, но и вообще почти любых рекуррентных последовательностей, просто потому количество возможных остатков конечно.

почему именно периодическая?

Xenius выше объяснил.

не вижу связи между конечность возможных остатков и (возможной!) их периодичностью.

О рекуррентности не забывай.

Не математическое решение задачи:

1) Найти период чисел fib(x-1)%m=0, fib(x)%m=1 перебором (опытное максимальное x = 4m, так что недолго)

2) Найти fib((n-1)%x+1)

В чем проблема-то?

Числа Фиббоначи могут быть получены как матричные элементы от степени матрицы [1, 1; 1, 0].

Возведение матрицы в n-ю степень может быть сделано не более чем за 2log_2 n шагов рекурсивно

Чтобы получать именно остатки, нужно использовать не простое вычисление матричных элементов как суммы произведений, а те же вычисления по модулю. Тогда на каждом шаге рекурсии все матрицы будут иметь матричные элементы, не превышающие по величине модуля.

Автор, а вы в курсе, что Эйлер в своё время показал, как найти n-е число Фибоначчи, не прибегая к этому к вычислению 100500 предыдущих.

как найти n-е число Фибоначчи, не прибегая к этому к вычислению 100500 предыдущих.

Ну найди ТСу число Фибоначчи для n=10^18

Вы как были безграмотным, так и будете, сколь большое n ни возьми. Вычисления по явной формуле во много раз быстрее, чем по рекуррентному соотношению.

Вычисления по явной формуле во много раз быстрее, чем по рекуррентному соотношению.

Бла бла бла. Предъяви число, балда.

приближенную формулу использовать можно

f_ = \left \lfloor \frac\left (\frac \right )^ + \frac \right \rfloor

Я подожду, пока ты по рекуррентной формуле его вычислишь, балда. А ну считать! А то год ждать мне неохота.

Проверил, порядок уже не совпадает.

Ну точно балда, какой год? У меня петафлопсного монстра под столом не завалялось. Для 10^18 количество операций как минимум того-же порядка.

Дело не во времени, а в том куда ты будешь складывать результат, хоть по какой формуле считай. F(n)

k^n ,т.е. для n=10^18 будет число порядка 10^18. Готовь 2-3 эксабайта памяти.

Вот и я говорю, нет, чтобы использовать формулу Бине для больших n:

И что, Бине? Это никак не отменяет необходимость записать полученное число, а по условию задачи число может быть до F(10^18). В лоб задача не решается, хоть ты тресни.

Мне лично пока ничего не приходит в голову, кроме как искать период последовательности по модулю m простым перебором (по рекуррентной формуле). Правда, m тоже не кислое 10^5, но есть надежда, что авторы задачи адекватные люди и такие периоды не будут слишком большими. Есть такая табличка http://webspace.ship.edu/msrenault/fibonacci/fiblist.htm, которая подкрепляет эту надежду.

Числа Фиббоначи могут быть получены как матричные элементы от степени матрицы [1, 1; 1, 0]. Возведение матрицы в n-ю степень может быть сделано не более чем за 2log_2 n шагов рекурсивно Чтобы получать именно остатки, нужно использовать не простое вычисление матричных элементов как суммы произведений, а те же вычисления по модулю. Тогда на каждом шаге рекурсии все матрицы будут иметь матричные элементы, не превышающие по величине модуля.

в принципе </thread>

надо только заметить, что следует вычислить периодичность остатков. А она может быть до (10^5)^2, то есть 10^10. Ибо считать в лоб может потребовать до 10^18 итераций, а это очень дохуя.

что-то я не уверен, что ты период правильно посчитаешь. он же зависит от двух последовательных чисел, а не от одного.

А я от двух и считаю.

Хотя да, с первого взгляда это не совсем очевидно. Лучше, наверное, так этот кусок переписать:

Для m = 10 ^ 5 и n = 10 ^ 18 получилось 46875

Не годится, нужно использовать BigMath. Иначе:

Что, видимо, неверно.

Тоже пришёл к этому решению. Теоретически максимально возможный период m^2, на практике возможно он не достигается ни для какого m. 10^10 перебрать два раза (первый раз, чтобы найти длиину цикла, второй раз, чтобы найти i-й элемент) на современном железе несложно. Ну и тоже интуитивно кажется, что длина периода будет гораздо короче, чем m^2, хотя аналитически не знаю, как доказать.

Отремонтировано

Теоретически максимально возможный период m^2

Вики гласит, что больше 6m не бывает.

Плюсую. Правильное решение.

Какое то непонятное решение. Что за вычисления матричных произведений по модулю, да ещё и за 2log2 n шагов? Код покажете?

Вот полное решение задачи на octave

Работает до n <=2^63 \approx 9x10¹⁸

диагональные элементы суть F[n+1] mod k, F[n-1] mod k, недиагональный — F[n] mod k

Немного наврал: работает для n<=2^53 \approx 9x10¹⁵ из-за того, что октава представляет все числа в double формате, что дает только 53 двоичных значащих цифр.

Но по этому прототипу легко переписать на C/C++ с 64-битными целыми

1. число отстатков от m всего m (0.. m-1)

2. функция берёт некоторое число(T) аргументов из конечного(M) и выдаёт из конечного

очевидно , что цикл не длинее M**T для любой функции.

для фибоначи не длинее m**2 .

Решение на Питоне (спасибо за подсказку про Пизано)

P.S. привет, господа из CompScience Center.

Объяснение. Берешь линейное реккурентное соотношение (по условию даны коэффициенты): x[n+1] = a[0]*x[n]+. +a[k]*x[n-k],и рассматриваешь вектор X_k такого вида: X[k] = (x[k] x[k-1]. x[0])и матрицу А строишь так, чтобы X[k+1] = X[k]*A: в первом столбце — коэффициенты уравнения («считаем очередное значение последовательности»), остальная матрица диагонально единицами заполнена от левого угла («сдвигаем вектор вправо, затирая ненужный x[0]»). Другими словами, в матричном виде записываешь действия, которые производятся при одной итерации линейного вычисления элементов последовательности. Если тебе надо посчитать x[n], то вместо того, чтобы множить вектор X[k] на матрицу (n-k) раз последовательно, возводишь ее в степень двоичным алгоритмом, а потом умножаешь вектор на нее.

В задаче критично, чтобы ответ был по модулю, иначе быстрое возведение в степень будет требовать реализации длинного умножения, и не факт, что подход окажется быстрее линейного вычисления.

📎📎📎📎📎📎📎📎📎📎