Project Euler Problem 989
Write Fn for the n-th Fibonacci number, with F1 = F2 = 1 and F{n+1} = Fn + F{n-1}.
Solution
Answer: 680057396
Using the arithmetic structure of the congruence
$$x^2\equiv x+1 \pmod n,$$
one shows that $G(n)$ is multiplicative and corresponds to primitive representations by the quadratic form
$$Q(a,b)=a^2-ab-b^2.$$
Applying Binet’s formula modulo $10^9+9$,
$$F_n=\frac{\varphi^n-\psi^n}{\sqrt5},$$
the problem reduces to evaluating weighted lattice sums over primitive points of $Q(a,b)\le L$, with Möbius inversion removing the coprimality condition.
After diagonalising
$$4Q(a,b)=(2a-b)^2-5b^2,$$
the computation can be performed in $O(\sqrt L\log L)$ time using the two parity branches and sliding-window accumulation described in the hints.
The implementation reproduces the required check value
$$\sum_{n\le 10^3}F_nG(n)\equiv 190950976 \pmod{10^9+9},$$
and then evaluates the full case $L=10^{14}$.
Answer: 680057396