Форум Всеукраїнської інтернет-олімпіади NetOI

jack_spektor написав:

Код:

Задания:

...

Задача 2:
Есть такая известная рекуррентная последовательность,которая 
называется числа Фибонначи.Каждый её елемент(кроме 
первых двух) есть суммой двух предыдущих.
    
F0=0;
F1=1;
Fn=Fn-1+Fn-2;

Надо найти остаток от деления N-го числа Фибонначи 
на натуральное число p.
Пример:
N        P        Ответ
0        7        0
6        16        8
12        10        4

Техничнеские ограничения:Существует прямая формула Н-го числа Фибонначи.(???)
...

!!! !!! !!! СУПЕР !!! !!! !!!

Фраза "Существует прямая формула Н-го числа Фибонначи" вообще-то не относится к условию. Вообще-то, это первая фраза из моего _РЕШЕНИЯ_... (книжечка, опубликованная прошлым летом в Шкільному світі)

Сразу же уточню, что эта фраза заканчивается как "... но для нас как программистов она совершенно бесполезна".
И предлагаются там три метода решения. Тот, на который тут стоИт ссылка на алголист, оценён как не очень сложный для реализации, но совершенно не придумывабельный. То есть, если его знать, то всё хорошо, но придумать такое самому не очень реально...
А оптимальным (по моему субьективному мнению) является следующий способ: если сразу считать всё по модулю p, последовательность получится циклической, вот и надо найти этот цикл, и считтать не до n-ого члена, а до (n mod c)-ого, где с -- длина цикла.

Кстати, когда я предлагал эту задачу на городе (Черкассы, 2000), то полных (правильных и эфеективных одновременно) решений не было вообще. Ни одного.

Andrey написав:

jack_spektor написав:

Что ты перебирать будешь.
Здесь если тупо перебирать то программа будет очень долго работать.
Смотри - при матрице размером 4*4 кол-во вариантов уже если не ошибаюсь n^16.
А дальше больше...

Я что вообще.... Я наверное знаю алгоритмы быстрых переборов...

Я её не решал.Но есть идея построить один такой квадрат и потом найти 4*Н квадратов путём поворота и обмена.