Тебе не нужно вычислять само число Фибоначчи, тебе достаточно вычислить отстаток от его деления на 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=10^18

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

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

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

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

f_{n} = \left \lfloor \frac{1}{\sqrt{5}}\left (\frac{1+\sqrt{5}}{2} \right )^{n} + \frac{1}{2} \right \rfloor

http://upload.wikimedia.org/math/e/c/2/ec2d778efb43ac887c327610746f8a15.png

1,85477076894719862121901385214e+37
проверяй :)

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

проверяй :)

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

А то год ждать мне неохота.

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

Дело не во времени, а в том куда ты будешь складывать результат, хоть по какой формуле считай. F(n)~k^n ,т.е. для n=10^18 будет число порядка 10^18. Готовь 2-3 эксабайта памяти.

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

F_n \sim \frac{\left( \frac{1 + \sqrt{5}}{2} \right)^n}{\sqrt{5}}

И что, Бине? Это никак не отменяет необходимость записать полученное число, а по условию задачи число может быть до 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 итераций, а это очень дохуя.

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

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

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

$fibprev = $fibk;
$fibcur = ($fibk + $fibk1) % $m;
$period = 1;
while(1) {
  last if ($fibcur == $fibk) and ($fibprev == $fibk1);

Период Пизано, кмк, поможет: http://ru.wikipedia.org/wiki/Период_Пизано

Вот жеж решение вроде: http://habrahabr.ru/post/91296/

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

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

$ ./fibo.pl 100000000000000000000000000000000000000000000000000000000000001 1000
n = 100000000000000000000000000000000000000000000000000000000000001 m = 1000 k = 16 fibk = 987 fibk1 = 610 period = 1500
Modulus = 120

$ ./fibo.pl 100000000000000000000000000000000000000000000000000000000000005 1000
n = 100000000000000000000000000000000000000000000000000000000000005 m = 1000 k = 16 fibk = 987 fibk1 = 610 period = 1500
Modulus = 120

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

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

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

#!/usr/bin/perl
use Math::BigInt;

$n = Math::BigInt->new($ARGV[0]);
$m = $ARGV[1];

$k = int(log($m*sqrt(5))/log((1 + sqrt(5))/2));
$fibk = int(0.5 + ((1 + sqrt(5))/2)**$k/sqrt(5));
$fibk1 = int(0.5 + ((1 + sqrt(5))/2)**($k - 1)/sqrt(5));

$fibprev = $fibk;
$fibcur = ($fibk + $fibk1) % $m;
$period = 1;
while(1) {
  last if ($fibcur == $fibk) and ($fibprev == $fibk1);
  $fibnext = ($fibcur + $fibprev) % $m;
  $fibprev = $fibcur;
  $fibcur = $fibnext;
  $period++;
};

print "n = $n m = $m k = $k fibk = $fibk fibk1 = $fibk1 period = $period\n";
$n->bsub($k);
$skip = $n->bmod($period);
$fibcur = $fibk;
$fibprev = $fibk1;
while ($skip) {
  $fibnext = ($fibcur + $fibprev) % $m;
  $fibprev = $fibcur;
  $fibcur = $fibnext;
  $skip--;
};
printf "Modulus = $fibcur\n";

./fibo.pl 100000000000000000 100000
n = 100000000000000000 m = 100000 k = 25 fibk = 75025 fibk1 = 46368 period = 150000
Modulus = 46875
./fibo.pl 100000000000000000000000000000000000000000000000000000000000001 1000
n = 100000000000000000000000000000000000000000000000000000000000001 m = 1000 k = 16 fibk = 987 fibk1 = 610 period = 1500
Modulus = 501
./fibo.pl 100000000000000000000000000000000000000000000000000000000000005 1000
n = 100000000000000000000000000000000000000000000000000000000000005 m = 1000 k = 16 fibk = 987 fibk1 = 610 period = 1500
Modulus = 130

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

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

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

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

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

function [A] = fib_mod (n, k)
  
  if (n >= 2)
    nn = fix(n/2);
    mm = n - nn;
    if (nn == mm)
      A = mod(fib_mod(nn, k)^2, k);
    else
      A = mod(fib_mod(nn, k)*fib_mod(mm, k), k);
    endif
  else 
    A = [1,1; 1,0];
  endif
  
endfunction

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

Пример:

octave:66> tic; fib_mod(2^63, 100001), toc
ans =

    5930   78715
   78715   27216

Elapsed time is 0.029707 seconds.

диагональные элементы суть 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 .

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

import sys

lineIn = sys.stdin.readline().split(" ")
n = int(lineIn[0])
m = int(lineIn[1])

fibPrev = 0
fib = 1
cached = [fibPrev, fib]

for curr in range(1, n):
    fibOld = fib
    fib = (fib + fibPrev) % m
    fibPrev = fibOld

    if fibPrev == 0 and fib == 1:
        cached.pop()
        break
    else:
        cached.append(fib)

offset = n % len(cached)
sys.stdout.write(str(cached[offset]))

python ~/Work/python/learning/fibonacci.py
1000000000001 99999
63715
Process finished with exit code 0

python ~/Work/python/learning/fibonacci.py
100000000000000000000000000001 100
1
Process finished with exit code 0

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

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

http://e-maxx.ru/algo/fibonacci_numbers

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

Объяснение. Берешь линейное реккурентное соотношение (по условию даны коэффициенты):
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) раз последовательно, возводишь ее в степень двоичным алгоритмом, а потом умножаешь вектор на нее.

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