l. Fibonacci Rabbits

Problem (Fibonacci, 1202). A pair of rabbits matures in one month and then produces a new pair every month. Starting with one newborn pair, how many pairs after $n$ months? $F_n$: $1,1,2,3,5,8,\dots$

pair<long long, long long> fibPair(long long n, long long m) {   // (F(n), F(n+1)) mod m, fast doubling
    if (n == 0) return {0, 1 % m};
    auto [a, b] = fibPair(n / 2, m);
    long long c = a * ((2 * b - a + m) % m) % m, d = (a * a + b * b) % m;
    return n % 2 ? make_pair(d, (c + d) % m) : make_pair(c, d);
}
long long pisano(long long m) {                    // period of F mod m (m >= 2), at most 6m
    long long a = 0, b = 1;
    for (long long i = 1; i <= 6 * m; i++) { long long t = (a + b) % m; a = b; b = t; if (a == 0 && b == 1) return i; }
    return -1;
}

Fact	Statement
fast doubling	$F_{2k}=F_k(2F_{k+1}-F_k)$, $F_{2k+1}=F_k^2+F_{k+1}^2$: $O(\log n)$
matrix form	${\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^n=\left(\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right)$
Pisano period	$F\mathrm{mod}m$ is periodic with period $\pi (m)\le 6m$: $\pi (10)=60$, $\pi (5)=20$
closed form	$F_n=({\phi }^n-{\psi }^n)/\sqrt{5}$ (Binet)

Proof: fast doubling and the Pisano period

From the matrix identity, $M^{2k}=(M^k{)}^2$; comparing entries gives $F_{2k}=F_k(F_{k+1}+F_{k-1})=F_k(2F_{k+1}-F_k)$ and $F_{2k+1}=F_{k+1}^2+F_k^2$. Periodicity. The pair $(F_n\mathrm{mod}m,F_{n+1}\mathrm{mod}m)$ takes at most $m^2$ values, and the map to the next pair is invertible ($F_{n-1}=F_{n+1}-F_n$), so the sequence of pairs is purely periodic and returns to $(0,1)$. The bound $\pi (m)\le 6m$ is a known theorem (equality for $m=2\cdot 5^k$). Checked against the iterative recurrence for several moduli and the periods $\pi (2)=3$, $\pi (5)=20$, $\pi (10)=60$.