Последние 40 цифр числа Фибоначчи, (Олимпиадная задача) Опции

[Гость]

Вот недавно встертил интересную задачку:
Нужно вывести последние 40 цифр n-ого числа фибонначи,
где n<10^18, вот и все

[Lapp]

Altair, ты гений!
Про формулу Бине я однозначно забыл [жжет лист бумаги, собирает пепел и посыпает голову]... А она ведь дает точное значение до последнего знака!

Но с нахрапа все равно не получается взять. Там фигурирует n-ая степень выражения, содержащего Sqrt(5). Если бы был просто корень из пяти, без слагаемых - то просто поделил n на два, потом дихотомией вычислить 5^(n/2). При этом n должно быть четным, но это ерунда - нечетное ЧФ вычислим по двум боковым четным. Вычислять в лоб (брать корень, прибавлять 1, делить пополам и возводить в степень дихотомическим умножением) нельзя, т.к. вычислять корень придется с точностью до 10^18 знаков..

Думаем.. [скрип мозгов за кадром]