Требуется найти последнюю цифру n-го числа Фибоначчи. Оптимизация алгоритма

Есть задача "Требуется найти последнюю цифру n-го числа Фибоначчи." по адресу http://acmp.ru/?main=task&id_task=623
Мое решение такое ( не знаю насколько этично выкладывать код решения в паблик )
#include #include
using namespace std;
int main(){ int a=1, b=1, c=a+b, n; cin >> n; if (n <= 1) c = 1; else for (int i = 2; i <= n; i++){ c = (a + b) % 10; a = b; b = c; } cout << c % 10; return 0; }
Результат: Время выполнения 0,858 Память 772 Кб
Согласно таблице на странице http://acmp.ru/index.asp?main=bstatus&id_t=623&lang=CPP за счет небольшого увеличения расхода памяти как то умудряются вложиться в 1-2 секунды. С одной стороны может быть мне подсунули входное число 1000, а другим 10.
Есть идеи по повышению производительности?

Ответ

Цитата из википедии
Период чисел Фибоначчи по модулю натурального числа n называется периодом Пизано и обозначается π(n). Периоды Пизано π(n) образуют последовательность: 1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … (последовательность A001175 в OEIS) В частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом π(10)=60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом π(100)=300, последние три цифры — с периодом π(1000)=1500, последние четыре — с периодом π(10000)=15000, последние пять — с периодом π(100000)=150000 и т. д.
Что такое период Пизано понятно из таблицы для π(4):
n | 1 2 3 4 5 6 | 7 8 9 ... F(n) | 0 1 1 2 3 5 | 8 13 21 ... F(n) mod 4 | 0 1 1 2 3 1 | 0 1 1 ...
То есть π(4) = 6, а именно: остатки от деления чисел Фибоначчи на 4 повторяются с периодом 6.
Как это применить для решения задачи подумайте сами.