# Fibonacci de 10¹⁸ em 84 multiplicações

> Toda recorrência linear pode ser escrita como multiplicação de matrizes. E matrizes podem ser elevadas a uma potência rápido.

- Autor: Marcello Oliveira (https://mrcll.me/about/)
- Publicado: 2 de nov. de 2026
- Temas: ICPC, Fundamentos
- URL: https://mrcll.me/pt/stories/linear-recurrences-log-time/

Qual é o 10¹⁸-ésimo número de Fibonacci, módulo algo razoável? Um loop ainda estaria rodando muito depois do fim da maratona. Dá para chegar lá com 84 multiplicações.

Uma recorrência linear é uma sequência em que cada termo é uma combinação linear dos anteriores, e Fibonacci é o exemplo famoso. Qualquer passo assim pode ser escrito como uma matriz T vezes um vetor com os termos recentes. Aplicar T uma vez anda a sequência um passo. Aplicar duas, T², anda dois. E T^(n−1), aplicada a f(0) e f(1), que você já conhece, chega em f(n).

Então a pergunta vira: quão rápido dá para elevar uma matriz a uma potência? Você não precisa de n multiplicações para chegar a xⁿ. De x sai x², de x² sai x⁴, de x⁴ sai x⁸. Qualquer expoente é uma soma dessas potências de dois, lida direto dos seus dígitos binários. Elevar ao quadrado transforma n passos em uns log n.

> Figura interativa (Recurrence): use a versão web em https://mrcll.me/pt/stories/linear-recurrences-log-time/

O loop precisa de 10¹⁸ passos; a matriz precisa de 84 multiplicações. Quando algo cresce um passo de cada vez, procure a forma que dobra. Quase sempre existe uma.