The quantity to compute is
\[ \sum_{n=1}^{L} F_n G(n) \pmod{10^9+9}, \qquad L=10^{14}, \]
where \(F_n\) is the Fibonacci sequence and \(G(n)\) counts the residue classes \(x \pmod n\) satisfying
\[ x^2 \equiv x+1 \pmod n. \]
The published checkpoint is
\[ \sum_{n=1}^{10^3} F_n G(n)\equiv 190950976 \pmod{10^9+9}. \]
A direct sweep up to \(10^{14}\) is hopeless, so the solution rewrites \(G(n)\) in arithmetic terms, turns the Fibonacci weight into exponential weights via Binet's formula, and then evaluates the resulting sums with Möbius inversion and a sliding-window count for a binary quadratic form.
The congruence is the same as
\[ x^2-x-1 \equiv 0 \pmod n, \]
whose discriminant is \(5\). That immediately explains the local structure.
For \(2^e\) there are no solutions, so \(G(2^e)=0\). For \(5\) there is exactly one solution, namely \(x\equiv 3 \pmod 5\), but it does not lift to \(25\), so
\[ G(5)=1, \qquad G(5^e)=0 \ \text{ for } e\ge 2. \]
For an odd prime \(p\neq 5\), the polynomial has roots modulo \(p\) exactly when \(5\) is a quadratic residue modulo \(p\). By quadratic reciprocity this happens precisely for
\[ p\equiv 1,4 \pmod 5. \]
In that case there are two distinct roots modulo \(p\), the derivative \(2x-1\) is nonzero at each root, and Hensel lifting gives two roots modulo every \(p^e\). If \(p\equiv 2,3 \pmod 5\), there are no roots at any power of \(p\). Hence
\[ G(p^e)= \begin{cases} 2, & p\equiv 1,4 \pmod 5,\\ 0, & p\equiv 2,3 \pmod 5, \end{cases} \qquad (p\neq 5,\ p \text{ odd}). \]
By the Chinese remainder theorem, \(G\) is multiplicative. Therefore, if
\[ n=5^\varepsilon \prod_{i=1}^{k} p_i^{a_i}\prod_{j=1}^{m} q_j^{b_j}, \]
where every \(p_i\equiv 1,4 \pmod 5\) and every \(q_j\) is either \(2\) or congruent to \(2\) or \(3\) modulo \(5\), then \(G(n)=0\) unless \(m=0\) and \(\varepsilon\in\{0,1\}\). In the surviving case,
\[ G(n)=2^k. \]
The next step moves to the quadratic ring generated by a root of \(t^2-t-1\). Let \(\varphi\) and \(\psi=1-\varphi\) be the two roots of \(t^2-t-1=0\), so \(\varphi^2=\varphi+1\). In the ring \(\mathbb Z[\varphi]\), the norm of \(a-b\varphi\) is
\[ N(a-b\varphi)=(a-b\varphi)(a-b\psi)=a^2-ab-b^2. \]
This binary quadratic form is exactly the arithmetic object used by the solver:
\[ Q(a,b)=a^2-ab-b^2. \]
The prime factors that contribute to \(G(n)\) are precisely the primes that split in \(\mathbb Z[\varphi]\). Choosing one root of \(x^2-x-1\) at each split prime power is equivalent to choosing one prime factor above each rational prime. Multiplying those local choices produces an algebraic integer of norm \(n\).
Two issues remain: units and non-primitive representations. Multiplying by a unit does not change the norm, so one imposes a reduction region to select a single representative. The implementations use the classical reduced region
\[ a\ge 2b>0. \]
Also, if \(\gcd(a,b)>1\), then the representation is not primitive and corresponds to extra square factors. After enforcing both conditions, one obtains the key identity
\[ G(n)=\#\{(a,b):\ a\ge 2b>0,\ \gcd(a,b)=1,\ Q(a,b)=n\}. \]
The modulus \(10^9+9\) is prime, \(5\) has a square root modulo this prime, and the two modular roots \(\varphi,\psi\) of \(t^2-t-1\) satisfy
\[ \varphi\psi=-1. \]
So Binet's formula is valid in the finite field:
\[ F_n=\frac{\varphi^n-\psi^n}{\sqrt 5}. \]
That converts the original sum into two weighted counts of quadratic-form values. Define
\[ P_w(L)= \sum_{\substack{a\ge 2b>0\\ \gcd(a,b)=1\\ Q(a,b)\le L}} w^{Q(a,b)}. \]
Then the desired answer is
\[ \sum_{n\le L} F_n G(n) = \frac{P_\varphi(L)-P_\psi(L)}{\sqrt 5} \pmod{10^9+9}. \]
The form \(Q\) is homogeneous of degree two:
\[ Q(ga,gb)=g^2Q(a,b). \]
Let
\[ A_w(L)= \sum_{\substack{a\ge 2b>0\\ Q(a,b)\le L}} w^{Q(a,b)} \]
be the same sum without \(\gcd(a,b)=1\). Möbius inversion then gives
\[ P_w(L)= \sum_{g\le \sqrt L} \mu(g)\, A_{w^{g^2}}\!\left(\left\lfloor \frac{L}{g^2}\right\rfloor\right). \]
So the primitive count is recovered by inclusion-exclusion over the common divisor \(g\).
The decisive algebraic identity is
\[ 4Q(a,b)=(2a-b)^2-5b^2. \]
Set
\[ u=2a-b,\qquad v=b. \]
Because \(a\ge 2b>0\), we have \(u\ge 3v>0\). Also \(u\equiv v \pmod 2\), so only two parity branches occur.
If \(u=2m\) and \(v=2t\), then
\[ Q(a,b)=m^2-5t^2, \qquad m\ge 3t, \qquad t\ge 1. \]
If \(u=2m+1\) and \(v=2t+1\), then
\[ Q(a,b)=m(m+1)-5t(t+1)-1, \qquad m\ge 3t+1, \qquad t\ge 0. \]
Therefore \(A_w(L)\) is the sum of two one-dimensional window sums:
\[ \sum_{t\ge 1} \sum_{m=3t}^{\lfloor \sqrt{L+5t^2}\rfloor} w^{m^2-5t^2}, \]
\[ \sum_{t\ge 0} \sum_{m=3t+1}^{\left\lfloor(\sqrt{4L+20t^2+20t+5}-1)/2\right\rfloor} w^{m(m+1)-5t(t+1)-1}. \]
Since \(11\equiv 1 \pmod 5\), there are two solutions of \(x^2\equiv x+1 \pmod{11}\), namely \(x\equiv 4\) and \(x\equiv 8\). So \(G(11)=2\).
The reduced primitive representations of \(11\) by \(Q(a,b)\) are
\[ Q(4,1)=16-4-1=11, \qquad Q(5,2)=25-10-4=11. \]
The first pair lands in the odd branch: \((u,v)=(2\cdot 4-1,1)=(7,1)\), so \(u=2m+1\), \(v=2t+1\) with \((m,t)=(3,0)\), and indeed
\[ m(m+1)-5t(t+1)-1=3\cdot 4-0-1=11. \]
The second pair lands in the even branch: \((u,v)=(8,2)\), so \((m,t)=(4,1)\), and
\[ m^2-5t^2=16-5=11. \]
This small case shows why the pair count agrees with \(G(n)\) and why both parity branches are needed in the final summation.
The C++, Python, and Java implementations begin by working modulo \(10^9+9\). They verify that the chosen modular constants really satisfy \(\sqrt 5^2=5\), \(\varphi^2=\varphi+1\), \(\psi^2=\psi+1\), and \(\varphi\psi=-1\). They also compare three views of the problem on small inputs: direct brute force for the congruence, the prime-factor formula for \(G(n)\), and the reduced-pair count for the quadratic form. Finally, they check the published sample sum for \(L=10^3\).
For a fixed weight \(w\), the implementation computes \(A_w(L)\) by scanning the two parity branches separately. It does not recompute \(w^{m^2}\) or \(w^{m(m+1)}\) from scratch. Instead it updates these powers multiplicatively, using the identities
\[ w^{(m+1)^2}=w^{m^2}w^{2m+1}, \qquad w^{(m+1)(m+2)}=w^{m(m+1)}w^{2m+2}. \]
As \(t\) grows, the allowed interval of \(m\) moves to the right. The implementation keeps a running window sum: new terms are appended when the upper bound increases, and expired terms are removed when the lower bound advances. Each admissible power enters once and leaves once.
After that, the implementation iterates over \(g\le \sqrt L\) with \(\mu(g)\neq 0\), evaluates the previous routine at the scaled limit \(\lfloor L/g^2\rfloor\), and combines the results with the Möbius sign. It precomputes the sequences \(\varphi^{g^2}\) and \(\varphi^{-g^2}\), which are enough for both branches because
\[ \psi=-\varphi^{-1}. \]
So \(\psi^{g^2}\) differs from \(\varphi^{-g^2}\) only by the parity-dependent sign of \(g^2\). The final step subtracts the \(\psi\)-sum from the \(\varphi\)-sum and multiplies by \(1/\sqrt 5\). The C++ and Java implementations can split the Möbius range across threads, while the Python implementation supports the same mathematics either serially or across processes.
The precomputed Möbius array and the tables of \(\varphi^{g^2}\) and \(\varphi^{-g^2}\) have size \(O(\sqrt L)\), so memory usage is \(O(\sqrt L)\).
For one fixed \(g\), the scaled limit is \(L/g^2\), and the two sliding-window branches together cost \(O(\sqrt{L/g^2})=O(\sqrt L/g)\). Summing over all \(g\le \sqrt L\) yields
\[ O\!\left(\sum_{g\le \sqrt L}\frac{\sqrt L}{g}\right) =O(\sqrt L\log L). \]
That is the reason the method can handle \(L=10^{14}\): it never iterates over all \(n\le L\), and it never enumerates all primitive pairs individually.
Gesucht ist die Summe
\[ \sum_{n=1}^{L} F_n G(n)\pmod{10^9+9}, \qquad L=10^{14}, \]
wobei \(F_n\) die Fibonacci-Zahlen sind und \(G(n)\) die Anzahl der Restklassen \(x \pmod n\) mit
\[ x^2 \equiv x+1 \pmod n \]
bezeichnet. Als Kontrollwert ist gegeben
\[ \sum_{n=1}^{10^3} F_n G(n)\equiv 190950976 \pmod{10^9+9}. \]
Eine direkte Summation bis \(10^{14}\) ist ausgeschlossen. Die Lösung zerlegt deshalb zuerst \(G(n)\) lokal nach Primzahlpotenzen, übersetzt die Fibonacci-Gewichte mit der Binet-Formel in Exponentialgewichte und wertet die entstehenden Summen mithilfe einer quadratischen Form, der Möbius-Inversion und gleitender Fenster aus.
Die Kongruenz ist äquivalent zu
\[ x^2-x-1 \equiv 0 \pmod n, \]
und ihr Diskriminant ist \(5\). Dadurch wird das Verhalten modulo Primzahlpotenzen vollständig bestimmt.
Für \(2^e\) gibt es keine Lösungen, also \(G(2^e)=0\). Für \(5\) existiert genau eine Lösung, nämlich \(x\equiv 3 \pmod 5\), aber diese hebt sich nicht auf \(25\) an. Daher gilt
\[ G(5)=1, \qquad G(5^e)=0 \ \text{ für } e\ge 2. \]
Für ungerade Primzahlen \(p\neq 5\) existieren Lösungen modulo \(p\) genau dann, wenn \(5\) ein quadratischer Rest modulo \(p\) ist. Nach quadratischer Reziprozität ist das genau für
\[ p\equiv 1,4 \pmod 5 \]
der Fall. Dann gibt es zwei einfache Nullstellen modulo \(p\), und Hensel-Liftung hebt beide eindeutig auf jedes \(p^e\) an. Für \(p\equiv 2,3 \pmod 5\) gibt es überhaupt keine Lösungen. Also
\[ G(p^e)= \begin{cases} 2, & p\equiv 1,4 \pmod 5,\\ 0, & p\equiv 2,3 \pmod 5, \end{cases} \qquad (p\neq 5,\ p \text{ ungerade}). \]
Mit dem chinesischen Restsatz folgt, dass \(G\) multiplikativ ist. Schreibt man
\[ n=5^\varepsilon \prod_{i=1}^{k} p_i^{a_i}\prod_{j=1}^{m} q_j^{b_j}, \]
wobei alle \(p_i\equiv 1,4 \pmod 5\) und jedes \(q_j\) entweder \(2\) oder zu \(2\) bzw. \(3\) modulo \(5\) kongruent ist, dann ist \(G(n)=0\), außer wenn \(m=0\) und \(\varepsilon\in\{0,1\}\). Im verbleibenden Fall gilt
\[ G(n)=2^k. \]
Nun wechselt man in den quadratischen Ring, der von einer Nullstelle von \(t^2-t-1\) erzeugt wird. Seien \(\varphi\) und \(\psi=1-\varphi\) die beiden Nullstellen, also \(\varphi^2=\varphi+1\). In \(\mathbb Z[\varphi]\) ist die Norm von \(a-b\varphi\)
\[ N(a-b\varphi)=(a-b\varphi)(a-b\psi)=a^2-ab-b^2. \]
Damit erscheint die zentrale binäre quadratische Form
\[ Q(a,b)=a^2-ab-b^2. \]
Genau die Primzahlen, die zu \(G(n)\) beitragen, zerfallen in \(\mathbb Z[\varphi]\). Die Wahl einer lokalen Lösung von \(x^2-x-1\) für jede zerfallene Primzahlpotenz entspricht der Wahl eines Primfaktors über dieser rationalen Primzahl. Das Produkt dieser lokalen Entscheidungen liefert ein algebraisches Integer mit Norm \(n\).
Um Mehrfachdarstellungen zu beseitigen, muss man Einheiten und nichtprimitive Darstellungen kontrollieren. Multiplikation mit einer Einheit ändert die Norm nicht, daher wählt man einen Reduktionsbereich. Die Implementierungen benutzen
\[ a\ge 2b>0. \]
Zusammen mit der Bedingung \(\gcd(a,b)=1\) ergibt sich die zentrale Identität
\[ G(n)=\#\{(a,b):\ a\ge 2b>0,\ \gcd(a,b)=1,\ Q(a,b)=n\}. \]
Da der Modul \(10^9+9\) prim ist, \(5\) darin eine Quadratwurzel besitzt und die modularen Werte \(\varphi,\psi\) die Gleichung \(t^2-t-1=0\) erfüllen, gilt auch im endlichen Körper die Binet-Formel:
\[ F_n=\frac{\varphi^n-\psi^n}{\sqrt 5}, \qquad \varphi\psi=-1. \]
Definiert man
\[ P_w(L)= \sum_{\substack{a\ge 2b>0\\ \gcd(a,b)=1\\ Q(a,b)\le L}} w^{Q(a,b)}, \]
dann wird die gesuchte Summe zu
\[ \sum_{n\le L} F_n G(n) = \frac{P_\varphi(L)-P_\psi(L)}{\sqrt 5} \pmod{10^9+9}. \]
Wegen der Homogenität zweiten Grades gilt
\[ Q(ga,gb)=g^2Q(a,b). \]
Ohne Koprimalitätsbedingung sei
\[ A_w(L)= \sum_{\substack{a\ge 2b>0\\ Q(a,b)\le L}} w^{Q(a,b)}. \]
Dann liefert die Möbius-Inversion
\[ P_w(L)= \sum_{g\le \sqrt L} \mu(g)\, A_{w^{g^2}}\!\left(\left\lfloor \frac{L}{g^2}\right\rfloor\right). \]
Primitive Darstellungen entstehen also durch ein Einbeziehen-und-Ausschließen über den gemeinsamen Teiler \(g\).
Der entscheidende Umformungsschritt ist
\[ 4Q(a,b)=(2a-b)^2-5b^2. \]
Setzt man
\[ u=2a-b,\qquad v=b, \]
so folgt aus \(a\ge 2b>0\), dass \(u\ge 3v>0\), und außerdem \(u\equiv v\pmod 2\). Daraus entstehen genau zwei Paritätszweige.
Für \(u=2m\), \(v=2t\) erhält man
\[ Q(a,b)=m^2-5t^2, \qquad m\ge 3t, \qquad t\ge 1. \]
Für \(u=2m+1\), \(v=2t+1\) folgt
\[ Q(a,b)=m(m+1)-5t(t+1)-1, \qquad m\ge 3t+1, \qquad t\ge 0. \]
Somit zerfällt \(A_w(L)\) in zwei eindimensionale Fenstersummen:
\[ \sum_{t\ge 1} \sum_{m=3t}^{\lfloor \sqrt{L+5t^2}\rfloor} w^{m^2-5t^2}, \]
\[ \sum_{t\ge 0} \sum_{m=3t+1}^{\left\lfloor(\sqrt{4L+20t^2+20t+5}-1)/2\right\rfloor} w^{m(m+1)-5t(t+1)-1}. \]
Da \(11\equiv 1 \pmod 5\), besitzt \(x^2\equiv x+1 \pmod{11}\) genau zwei Lösungen, nämlich \(x\equiv 4\) und \(x\equiv 8\). Also ist \(G(11)=2\).
Die reduzierten primitiven Darstellungen von \(11\) durch \(Q(a,b)\) sind
\[ Q(4,1)=16-4-1=11, \qquad Q(5,2)=25-10-4=11. \]
Das Paar \((4,1)\) liegt im ungeraden Zweig: \((u,v)=(7,1)\), also \((m,t)=(3,0)\), und damit
\[ m(m+1)-5t(t+1)-1=3\cdot 4-0-1=11. \]
Das Paar \((5,2)\) liegt im geraden Zweig: \((u,v)=(8,2)\), also \((m,t)=(4,1)\), und
\[ m^2-5t^2=16-5=11. \]
Das Beispiel zeigt konkret, warum die Zählung der Paare mit \(G(n)\) übereinstimmt und warum beide Paritätszweige benötigt werden.
Die C++-, Python- und Java-Implementierungen arbeiten vollständig modulo \(10^9+9\). Zuerst wird überprüft, dass die verwendeten modularen Konstanten wirklich \(\sqrt 5\), \(\varphi\) und \(\psi\) repräsentieren, also \(\sqrt 5^2=5\), \(\varphi^2=\varphi+1\), \(\psi^2=\psi+1\) und \(\varphi\psi=-1\) gilt. Danach werden drei Sichtweisen auf kleine Werte gegeneinander geprüft: direkte Brute-Force-Zählung der Lösungen, die Primfaktorformel für \(G(n)\) und die reduzierte Darstellung durch die quadratische Form. Abschließend wird die veröffentlichte Beispielsummenformel für \(L=10^3\) verifiziert.
Für ein festes Gewicht \(w\) berechnet die Implementierung \(A_w(L)\), indem sie die beiden Paritätszweige getrennt durchläuft. Dabei werden die Folgen \(w^{m^2}\) und \(w^{m(m+1)}\) nicht jedes Mal neu exponentiert, sondern multiplikativ fortgeschrieben:
\[ w^{(m+1)^2}=w^{m^2}w^{2m+1}, \qquad w^{(m+1)(m+2)}=w^{m(m+1)}w^{2m+2}. \]
Wenn \(t\) wächst, verschiebt sich das zulässige Intervall für \(m\). Die Implementierung hält daher eine laufende Fenstersumme: Neue Terme werden am rechten Rand hinzugefügt, abgelaufene Terme am linken Rand entfernt. Jeder zulässige Term tritt genau einmal ein und genau einmal wieder aus.
Danach iteriert die Implementierung über alle \(g\le \sqrt L\) mit \(\mu(g)\neq 0\), wertet die vorherige Routine bei \(\lfloor L/g^2\rfloor\) aus und kombiniert die Beiträge mit dem Vorzeichen von \(\mu(g)\). Vorab werden \(\varphi^{g^2}\) und \(\varphi^{-g^2}\) tabelliert. Das genügt auch für den \(\psi\)-Zweig, weil
\[ \psi=-\varphi^{-1} \]
gilt und sich \(\psi^{g^2}\) daher nur um ein paritätsabhängiges Vorzeichen von \(\varphi^{-g^2}\) unterscheidet. Zum Schluss wird die \(\psi\)-Summe von der \(\varphi\)-Summe abgezogen und mit \(1/\sqrt 5\) multipliziert. C++ und Java können den Möbius-Bereich zusätzlich auf mehrere Threads verteilen; Python kann dieselbe Rechnung seriell oder über Prozesse ausführen.
Das Möbius-Array sowie die Tabellen für \(\varphi^{g^2}\) und \(\varphi^{-g^2}\) haben Größe \(O(\sqrt L)\). Daher ist auch der Speicherverbrauch \(O(\sqrt L)\).
Für ein festes \(g\) beträgt die skalierte Schranke \(L/g^2\), und die beiden gleitenden Fenstersummen kosten zusammen \(O(\sqrt{L/g^2})=O(\sqrt L/g)\). Summiert man das über alle \(g\le \sqrt L\), erhält man
\[ O\!\left(\sum_{g\le \sqrt L}\frac{\sqrt L}{g}\right) =O(\sqrt L\log L). \]
Genau deshalb kann die Methode \(L=10^{14}\) bewältigen: Sie iteriert weder über alle \(n\le L\) noch über alle primitiven Darstellungen einzeln.
Hesaplanmak istenen toplam
\[ \sum_{n=1}^{L} F_n G(n)\pmod{10^9+9}, \qquad L=10^{14}, \]
şeklindedir. Burada \(F_n\) Fibonacci dizisi, \(G(n)\) ise
\[ x^2 \equiv x+1 \pmod n \]
denkliğini sağlayan artık sınıflarının sayısıdır. Verilen kontrol değeri
\[ \sum_{n=1}^{10^3} F_n G(n)\equiv 190950976 \pmod{10^9+9} \]
olduğundan çözüm önce bunu doğrular. Asıl zorluk, \(L=10^{14}\) için doğrudan toplamanın imkansız olmasıdır. Bu yüzden çözüm \(G(n)\)'i asal kuvvetler üzerinde çözümler, ardından Fibonacci ağırlığını Binet formülüyle üstel ağırlıklara çevirir ve geriye kalan işi ikili kuadratik form, Möbius tersleme ve kayan pencere toplamlarıyla bitirir.
Verilen kongruens
\[ x^2-x-1 \equiv 0 \pmod n \]
biçimine gelir ve diskriminantı \(5\)'tir. Yerel yapı buradan başlar.
\(2^e\) modunda çözüm yoktur; dolayısıyla \(G(2^e)=0\). \(5\) modunda tam bir çözüm vardır: \(x\equiv 3 \pmod 5\). Fakat bu kök \(25\)'e yükselmez. Bu yüzden
\[ G(5)=1, \qquad G(5^e)=0 \ \text{, } e\ge 2. \]
\(p\neq 5\) tek asal olsun. Mod \(p\)'de kök bulunması, \(5\)'in kare kalıntısı olmasına eşdeğerdir. Kuadratik karşılıklılık yasası bunu tam olarak
\[ p\equiv 1,4 \pmod 5 \]
durumuna indirger. Bu durumda mod \(p\)'de iki farklı kök vardır; türev \(2x-1\) bu köklerde sıfır olmadığı için Hensel kaldırması her kökü tüm \(p^e\)'lere tek biçimde taşır. Eğer \(p\equiv 2,3 \pmod 5\) ise hiçbir kuvvette çözüm yoktur. Sonuç olarak
\[ G(p^e)= \begin{cases} 2, & p\equiv 1,4 \pmod 5,\\ 0, & p\equiv 2,3 \pmod 5, \end{cases} \qquad (p\neq 5,\ p \text{ tek asal}). \]
Çin kalan teoremi ile \(G\) çarpımsal olur. Eğer
\[ n=5^\varepsilon \prod_{i=1}^{k} p_i^{a_i}\prod_{j=1}^{m} q_j^{b_j} \]
olup bütün \(p_i\)'ler \(1\) veya \(4\) mod \(5\), bütün \(q_j\)'ler ise ya \(2\) ya da \(2\) veya \(3\) mod \(5\) sınıfındaysa, \(G(n)\) ancak \(m=0\) ve \(\varepsilon\in\{0,1\}\) olduğunda sıfırdan farklı olabilir. Bu durumda
\[ G(n)=2^k \]
elde edilir.
Bir sonraki adım, \(t^2-t-1\)'in bir kökünü içeren kuadratik halka üzerine geçmektir. \(\varphi\) ve \(\psi=1-\varphi\) kökleri için \(\varphi^2=\varphi+1\) olur. \(\mathbb Z[\varphi]\) içinde \(a-b\varphi\) elemanının normu
\[ N(a-b\varphi)=(a-b\varphi)(a-b\psi)=a^2-ab-b^2 \]
şeklindedir. Böylece temel nesne
\[ Q(a,b)=a^2-ab-b^2 \]
kuadratik formudur.
\(G(n)\)'e katkı veren asallar tam olarak bu halkada ayrışan asallardır. Her ayrışan asal kuvvet için bir kök seçmek, bu asalın üzerinde bir asal çarpan seçmekle aynı bilgiyi taşır. Bütün yerel seçimler çarpılınca normu \(n\) olan bir cebirsel tamsayı elde edilir.
Fakat aynı normu veren eşdeğer temsiller vardır. Birimlerle çarpmak normu değiştirmez; bu yüzden tek bir temsil seçmek için indirgenmiş bölge
\[ a\ge 2b>0 \]
alınır. Ayrıca \(\gcd(a,b)=1\) koşulu ilkel temsilleri seçer. Sonuçta şu özdeşlik ortaya çıkar:
\[ G(n)=\#\{(a,b):\ a\ge 2b>0,\ \gcd(a,b)=1,\ Q(a,b)=n\}. \]
Modül \(10^9+9\) bir asaldır ve bu sonlu cisimde hem \(\sqrt 5\) hem de \(t^2-t-1\)'in iki kökü vardır. Ayrıca
\[ \varphi\psi=-1. \]
Dolayısıyla Binet formülü modüler ortamda da geçerlidir:
\[ F_n=\frac{\varphi^n-\psi^n}{\sqrt 5}. \]
Şimdi
\[ P_w(L)= \sum_{\substack{a\ge 2b>0\\ \gcd(a,b)=1\\ Q(a,b)\le L}} w^{Q(a,b)} \]
tanımlanırsa aranan toplam
\[ \sum_{n\le L} F_n G(n) = \frac{P_\varphi(L)-P_\psi(L)}{\sqrt 5} \pmod{10^9+9} \]
olur.
Form ikinci dereceden homojendir:
\[ Q(ga,gb)=g^2Q(a,b). \]
İlkel olma şartını geçici olarak kaldırıp
\[ A_w(L)= \sum_{\substack{a\ge 2b>0\\ Q(a,b)\le L}} w^{Q(a,b)} \]
dersek Möbius tersleme
\[ P_w(L)= \sum_{g\le \sqrt L} \mu(g)\, A_{w^{g^2}}\!\left(\left\lfloor \frac{L}{g^2}\right\rfloor\right) \]
eşitliğini verir. Böylece ortak bölen \(g\) olan tüm temsiller dahil-et/dışla mantığıyla temizlenir.
Ana cebirsel özdeşlik
\[ 4Q(a,b)=(2a-b)^2-5b^2 \]
olduğundan
\[ u=2a-b,\qquad v=b \]
değişkenleri alınır. \(a\ge 2b>0\) olduğu için \(u\ge 3v>0\) ve ayrıca \(u\equiv v \pmod 2\) elde edilir. Yani yalnızca iki parite kolu vardır.
\(u=2m\), \(v=2t\) için
\[ Q(a,b)=m^2-5t^2, \qquad m\ge 3t, \qquad t\ge 1. \]
\(u=2m+1\), \(v=2t+1\) için ise
\[ Q(a,b)=m(m+1)-5t(t+1)-1, \qquad m\ge 3t+1, \qquad t\ge 0. \]
Böylece \(A_w(L)\) iki adet tek boyutlu pencere toplamına ayrılır:
\[ \sum_{t\ge 1} \sum_{m=3t}^{\lfloor \sqrt{L+5t^2}\rfloor} w^{m^2-5t^2}, \]
\[ \sum_{t\ge 0} \sum_{m=3t+1}^{\left\lfloor(\sqrt{4L+20t^2+20t+5}-1)/2\right\rfloor} w^{m(m+1)-5t(t+1)-1}. \]
\(11\equiv 1 \pmod 5\) olduğundan \(x^2\equiv x+1 \pmod{11}\) denkleminin iki çözümü vardır: \(x\equiv 4\) ve \(x\equiv 8\). O halde \(G(11)=2\).
\(Q(a,b)\) formunun \(11\) için indirgenmiş ilkel temsilleri
\[ Q(4,1)=16-4-1=11, \qquad Q(5,2)=25-10-4=11 \]
şeklindedir.
\((4,1)\) çifti tek-tek koluna düşer: \((u,v)=(7,1)\), dolayısıyla \((m,t)=(3,0)\) ve
\[ m(m+1)-5t(t+1)-1=3\cdot 4-0-1=11. \]
\((5,2)\) çifti çift-çift koluna düşer: \((u,v)=(8,2)\), dolayısıyla \((m,t)=(4,1)\) ve
\[ m^2-5t^2=16-5=11. \]
Bu küçük örnek, hem parite ayrımının neden gerekli olduğunu hem de çift sayısının \(G(n)\) ile neden örtüştüğünü somut biçimde gösterir.
C++, Python ve Java uygulamaları önce mod \(10^9+9\) içinde çalışır. Kullandıkları sabitlerin gerçekten \(\sqrt 5\), \(\varphi\) ve \(\psi\) davranışı gösterdiğini; yani \(\sqrt 5^2=5\), \(\varphi^2=\varphi+1\), \(\psi^2=\psi+1\) ve \(\varphi\psi=-1\) olduğunu kontrol ederler. Sonra küçük girişlerde üç farklı bakış açısını karşılaştırırlar: kongruensin kaba kuvvet çözüm sayısı, \(G(n)\)'in asal çarpanlardan gelen formülü ve kuadratik form üzerindeki indirgenmiş ilkel çift sayısı. Son doğrulama, yayımlanmış örnek toplamı \(L=10^3\) için yeniden üretmektir.
Sabit bir \(w\) verildiğinde uygulama \(A_w(L)\)'yi iki parite kolunu ayrı ayrı tarayarak hesaplar. \(w^{m^2}\) ve \(w^{m(m+1)}\) değerleri her adımda baştan üs alınarak bulunmaz; bunun yerine
\[ w^{(m+1)^2}=w^{m^2}w^{2m+1}, \qquad w^{(m+1)(m+2)}=w^{m(m+1)}w^{2m+2} \]
geçişleri kullanılır. \(t\) arttıkça geçerli \(m\) aralığı sağa kayar. Uygulama bu yüzden bir pencere toplamı tutar: sağ uç büyüdükçe yeni terimler eklenir, sol uç ilerledikçe eski terimler çıkarılır. Her terim pencereye yalnızca bir kez girer ve bir kez çıkar.
Daha sonra uygulama \(\mu(g)\neq 0\) olan tüm \(g\le \sqrt L\) değerleri üzerinden geçer, önceki yordamı \(\lfloor L/g^2\rfloor\) sınırında çağırır ve katkıları Möbius işaretiyle toplar. \(\varphi^{g^2}\) ve \(\varphi^{-g^2}\) dizileri önceden hesaplanır. Bu iki tablo \(\psi\) tarafı için de yeterlidir, çünkü
\[ \psi=-\varphi^{-1} \]
olduğundan \(\psi^{g^2}\), \(\varphi^{-g^2}\)'den yalnızca \(g\)'nin paritesine bağlı bir işaretle ayrılır. Son adımda \(\varphi\)-ağırlıklı toplamdan \(\psi\)-ağırlıklı toplam çıkarılır ve sonuç \(1/\sqrt 5\) ile çarpılır. C++ ve Java sürümleri isterse Möbius aralığını iş parçacıklarına bölebilir; Python sürümü aynı hesabı seri ya da süreç tabanlı biçimde yapabilir.
Möbius dizisi ile \(\varphi^{g^2}\) ve \(\varphi^{-g^2}\) tabloları \(O(\sqrt L)\) boyutundadır. Bu yüzden bellek kullanımı \(O(\sqrt L)\) olur.
Sabit bir \(g\) için ölçeklenmiş üst sınır \(L/g^2\)'dir ve iki kayan pencere kolunun toplam maliyeti \(O(\sqrt{L/g^2})=O(\sqrt L/g)\) olur. Bunu tüm \(g\le \sqrt L\) üzerinde toplayınca
\[ O\!\left(\sum_{g\le \sqrt L}\frac{\sqrt L}{g}\right) =O(\sqrt L\log L) \]
elde edilir. Yöntemin \(L=10^{14}\) için çalışabilmesi tam olarak bundan gelir: ne tüm \(n\le L\) değerleri tek tek dolaşılır ne de tüm ilkel temsiller ayrı ayrı üretilir.
La suma buscada es
\[ \sum_{n=1}^{L} F_n G(n)\pmod{10^9+9}, \qquad L=10^{14}, \]
donde \(F_n\) es la sucesión de Fibonacci y \(G(n)\) cuenta las clases residuales \(x \pmod n\) que satisfacen
\[ x^2 \equiv x+1 \pmod n. \]
El valor de control publicado es
\[ \sum_{n=1}^{10^3} F_n G(n)\equiv 190950976 \pmod{10^9+9}. \]
No es viable recorrer todos los \(n\) hasta \(10^{14}\). La solución reescribe primero \(G(n)\) mediante aritmética local en potencias primas, luego convierte el peso Fibonacci en pesos exponenciales con la fórmula de Binet y finalmente evalúa las sumas restantes con inversión de Möbius y una cuenta por ventanas deslizantes asociada a una forma cuadrática binaria.
La congruencia se puede escribir como
\[ x^2-x-1 \equiv 0 \pmod n, \]
cuyo discriminante es \(5\). Eso determina el análisis local.
Para \(2^e\) no hay soluciones, así que \(G(2^e)=0\). Para \(5\) hay una única solución, \(x\equiv 3 \pmod 5\), pero no se levanta a \(25\). Por tanto,
\[ G(5)=1, \qquad G(5^e)=0 \ \text{ para } e\ge 2. \]
Si \(p\neq 5\) es impar, existen raíces módulo \(p\) exactamente cuando \(5\) es un residuo cuadrático módulo \(p\). Por reciprocidad cuadrática esto ocurre precisamente cuando
\[ p\equiv 1,4 \pmod 5. \]
Entonces hay dos raíces simples módulo \(p\), la derivada \(2x-1\) no se anula en ellas y el levantamiento de Hensel produce dos raíces módulo cada \(p^e\). Si \(p\equiv 2,3 \pmod 5\), no aparece ninguna raíz en ninguna potencia. En resumen,
\[ G(p^e)= \begin{cases} 2, & p\equiv 1,4 \pmod 5,\\ 0, & p\equiv 2,3 \pmod 5, \end{cases} \qquad (p\neq 5,\ p \text{ impar}). \]
Por el teorema chino del resto, \(G\) es multiplicativa. Si
\[ n=5^\varepsilon \prod_{i=1}^{k} p_i^{a_i}\prod_{j=1}^{m} q_j^{b_j}, \]
donde cada \(p_i\equiv 1,4 \pmod 5\) y cada \(q_j\) es \(2\) o bien satisface \(q_j\equiv 2,3 \pmod 5\), entonces \(G(n)=0\) salvo cuando \(m=0\) y \(\varepsilon\in\{0,1\}\). En ese caso
\[ G(n)=2^k. \]
El siguiente paso entra en el anillo cuadrático generado por una raíz de \(t^2-t-1\). Sean \(\varphi\) y \(\psi=1-\varphi\) las dos raíces, con \(\varphi^2=\varphi+1\). En \(\mathbb Z[\varphi]\), la norma de \(a-b\varphi\) es
\[ N(a-b\varphi)=(a-b\varphi)(a-b\psi)=a^2-ab-b^2. \]
Así aparece la forma cuadrática binaria central:
\[ Q(a,b)=a^2-ab-b^2. \]
Los primos que contribuyen a \(G(n)\) son exactamente los primos que se descomponen en \(\mathbb Z[\varphi]\). Elegir una raíz local de \(x^2-x-1\) en cada potencia prima descompuesta equivale a elegir uno de los factores primos sobre ese primo racional. Al multiplicar esas elecciones locales se obtiene un entero algebraico de norma \(n\).
Para eliminar duplicados hay que fijar representantes. Multiplicar por una unidad no cambia la norma, de modo que se impone la región reducida
\[ a\ge 2b>0. \]
Además, \(\gcd(a,b)=1\) selecciona las representaciones primitivas. El resultado es la identidad fundamental
\[ G(n)=\#\{(a,b):\ a\ge 2b>0,\ \gcd(a,b)=1,\ Q(a,b)=n\}. \]
Como \(10^9+9\) es primo, \(5\) tiene una raíz cuadrada módulo este primo y las raíces modulares \(\varphi,\psi\) de \(t^2-t-1\) cumplen
\[ \varphi\psi=-1. \]
Por eso la fórmula de Binet vale también en el cuerpo finito:
\[ F_n=\frac{\varphi^n-\psi^n}{\sqrt 5}. \]
Definimos
\[ P_w(L)= \sum_{\substack{a\ge 2b>0\\ \gcd(a,b)=1\\ Q(a,b)\le L}} w^{Q(a,b)}. \]
Entonces la suma pedida se transforma en
\[ \sum_{n\le L} F_n G(n) = \frac{P_\varphi(L)-P_\psi(L)}{\sqrt 5} \pmod{10^9+9}. \]
La forma es homogénea de grado dos:
\[ Q(ga,gb)=g^2Q(a,b). \]
Si quitamos la condición \(\gcd(a,b)=1\) y escribimos
\[ A_w(L)= \sum_{\substack{a\ge 2b>0\\ Q(a,b)\le L}} w^{Q(a,b)}, \]
la inversión de Möbius da
\[ P_w(L)= \sum_{g\le \sqrt L} \mu(g)\, A_{w^{g^2}}\!\left(\left\lfloor \frac{L}{g^2}\right\rfloor\right). \]
Así, la primitividad se recupera por inclusión-exclusión sobre el divisor común \(g\).
La identidad decisiva es
\[ 4Q(a,b)=(2a-b)^2-5b^2. \]
Tomamos
\[ u=2a-b,\qquad v=b. \]
Como \(a\ge 2b>0\), resulta \(u\ge 3v>0\), y además \(u\equiv v \pmod 2\). Solo aparecen dos ramas.
Si \(u=2m\) y \(v=2t\), entonces
\[ Q(a,b)=m^2-5t^2, \qquad m\ge 3t, \qquad t\ge 1. \]
Si \(u=2m+1\) y \(v=2t+1\), se obtiene
\[ Q(a,b)=m(m+1)-5t(t+1)-1, \qquad m\ge 3t+1, \qquad t\ge 0. \]
Por tanto \(A_w(L)\) se convierte en la suma de dos ventanas unidimensionales:
\[ \sum_{t\ge 1} \sum_{m=3t}^{\lfloor \sqrt{L+5t^2}\rfloor} w^{m^2-5t^2}, \]
\[ \sum_{t\ge 0} \sum_{m=3t+1}^{\left\lfloor(\sqrt{4L+20t^2+20t+5}-1)/2\right\rfloor} w^{m(m+1)-5t(t+1)-1}. \]
Como \(11\equiv 1 \pmod 5\), la congruencia \(x^2\equiv x+1 \pmod{11}\) tiene exactamente dos soluciones: \(x\equiv 4\) y \(x\equiv 8\). Por eso \(G(11)=2\).
Las representaciones primitivas reducidas de \(11\) por \(Q(a,b)\) son
\[ Q(4,1)=16-4-1=11, \qquad Q(5,2)=25-10-4=11. \]
La pareja \((4,1)\) cae en la rama impar: \((u,v)=(7,1)\), luego \((m,t)=(3,0)\), y
\[ m(m+1)-5t(t+1)-1=3\cdot 4-0-1=11. \]
La pareja \((5,2)\) cae en la rama par: \((u,v)=(8,2)\), luego \((m,t)=(4,1)\), y
\[ m^2-5t^2=16-5=11. \]
Este ejemplo muestra en una sola cifra por qué el conteo por pares coincide con \(G(n)\) y por qué las dos ramas de paridad son indispensables.
Las implementaciones en C++, Python y Java trabajan completamente módulo \(10^9+9\). Primero verifican que las constantes modulares elegidas realmente representan \(\sqrt 5\), \(\varphi\) y \(\psi\), es decir, que \(\sqrt 5^2=5\), \(\varphi^2=\varphi+1\), \(\psi^2=\psi+1\) y \(\varphi\psi=-1\). Después comparan tres descripciones del mismo objeto para valores pequeños: la fuerza bruta sobre la congruencia, la fórmula de factorización de \(G(n)\) y el recuento de pares reducidos de la forma cuadrática. Finalmente reproducen el valor de muestra para \(L=10^3\).
Para un peso fijo \(w\), la implementación calcula \(A_w(L)\) recorriendo por separado las dos ramas de paridad. No recalcula \(w^{m^2}\) ni \(w^{m(m+1)}\) desde cero; en cambio actualiza ambas secuencias multiplicativamente mediante
\[ w^{(m+1)^2}=w^{m^2}w^{2m+1}, \qquad w^{(m+1)(m+2)}=w^{m(m+1)}w^{2m+2}. \]
Cuando \(t\) aumenta, el intervalo permitido de \(m\) se desplaza a la derecha. La implementación mantiene una suma de ventana: añade nuevos términos cuando crece el extremo superior y elimina los que dejan de ser válidos cuando avanza el extremo inferior. Cada término entra una vez y sale una vez.
Luego la implementación recorre todos los \(g\le \sqrt L\) con \(\mu(g)\neq 0\), evalúa la rutina anterior con límite escalado \(\lfloor L/g^2\rfloor\) y combina las contribuciones con el signo de Möbius. También precomputa \(\varphi^{g^2}\) y \(\varphi^{-g^2}\). Eso basta para la rama de \(\psi\), porque
\[ \psi=-\varphi^{-1}, \]
de modo que \(\psi^{g^2}\) solo difiere de \(\varphi^{-g^2}\) por un signo que depende de la paridad de \(g\). Al final se resta la suma con peso \(\psi\) de la suma con peso \(\varphi\) y se multiplica por \(1/\sqrt 5\). Las versiones en C++ y Java pueden repartir el rango de Möbius entre varios hilos; la versión en Python puede hacer la misma cuenta en serie o con procesos.
El arreglo de Möbius y las tablas de \(\varphi^{g^2}\) y \(\varphi^{-g^2}\) ocupan \(O(\sqrt L)\) memoria, así que el uso total de memoria es \(O(\sqrt L)\).
Para un \(g\) fijo, el límite escalado es \(L/g^2\), y las dos ramas con ventanas deslizantes cuestan juntas \(O(\sqrt{L/g^2})=O(\sqrt L/g)\). Sumando sobre todos los \(g\le \sqrt L\) se obtiene
\[ O\!\left(\sum_{g\le \sqrt L}\frac{\sqrt L}{g}\right) =O(\sqrt L\log L). \]
Ese es el motivo por el que el método puede manejar \(L=10^{14}\): no itera sobre todos los \(n\le L\) y tampoco enumera una por una todas las parejas primitivas.
要求计算的量是
\[ \sum_{n=1}^{L} F_n G(n)\pmod{10^9+9}, \qquad L=10^{14}, \]
其中 \(F_n\) 是 Fibonacci 数列，\(G(n)\) 表示满足
\[ x^2 \equiv x+1 \pmod n \]
的模 \(n\) 剩余类个数。题目给出的检验值是
\[ \sum_{n=1}^{10^3} F_n G(n)\equiv 190950976 \pmod{10^9+9}. \]
由于 \(L=10^{14}\)，显然不能直接对所有 \(n\) 做枚举。真正可行的做法是：先把 \(G(n)\) 的结构分解到各个素数幂上，再用 Binet 公式把 Fibonacci 权重改写成指数权重，最后把整个问题转化为一个二元二次型的计数问题，并借助 Möbius 反演与滑动窗口求和来完成。
原同余式等价于
\[ x^2-x-1 \equiv 0 \pmod n, \]
它的判别式是 \(5\)。因此，局部行为完全由 \(5\) 在模各个素数时是否是平方剩余来决定。
对 \(2^e\) 来说没有解，所以 \(G(2^e)=0\)。对 \(5\) 来说恰好有一个解，即 \(x\equiv 3 \pmod 5\)，但这个解不能提升到 \(25\)，因此
\[ G(5)=1, \qquad G(5^e)=0 \ \text{ 当 } e\ge 2. \]
若 \(p\neq 5\) 是奇素数，那么模 \(p\) 有解当且仅当 \(5\) 是模 \(p\) 的平方剩余。由二次互反律可知，这恰好等价于
\[ p\equiv 1,4 \pmod 5. \]
在这种情况下，模 \(p\) 有两个不同的根，并且在每个根处导数 \(2x-1\) 都不为零，所以 Hensel 引理保证它们各自唯一提升到任意 \(p^e\)。若 \(p\equiv 2,3 \pmod 5\)，则任何 \(p^e\) 上都没有根。于是
\[ G(p^e)= \begin{cases} 2, & p\equiv 1,4 \pmod 5,\\ 0, & p\equiv 2,3 \pmod 5, \end{cases} \qquad (p\neq 5,\ p \text{ 为奇素数}). \]
再由中国剩余定理得到 \(G\) 是乘法函数。若
\[ n=5^\varepsilon \prod_{i=1}^{k} p_i^{a_i}\prod_{j=1}^{m} q_j^{b_j}, \]
其中所有 \(p_i\equiv 1,4 \pmod 5\)，而所有 \(q_j\) 不是 \(2\) 就满足 \(q_j\equiv 2,3 \pmod 5\)，那么只有在 \(m=0\) 且 \(\varepsilon\in\{0,1\}\) 时 \(G(n)\) 才可能非零。此时
\[ G(n)=2^k. \]
接下来要进入由 \(t^2-t-1\) 的根生成的二次整环。设 \(\varphi\) 与 \(\psi=1-\varphi\) 是这两个根，则 \(\varphi^2=\varphi+1\)。在 \(\mathbb Z[\varphi]\) 中，元素 \(a-b\varphi\) 的范数是
\[ N(a-b\varphi)=(a-b\varphi)(a-b\psi)=a^2-ab-b^2. \]
因此核心对象就是二元二次型
\[ Q(a,b)=a^2-ab-b^2. \]
恰好那些会给 \(G(n)\) 贡献根的素数，会在 \(\mathbb Z[\varphi]\) 中分裂。对每个分裂素数幂选择一个局部根，本质上等价于在该有理素数之上选择一个素因子。把这些局部选择乘起来，就会得到一个范数等于 \(n\) 的代数整数。
但这还不是唯一表示，因为单位元相乘不会改变范数，而且非原始表示会带来额外的平方公因子。为此需要选一个标准区域作为代表。实现采用的是经典约化条件
\[ a\ge 2b>0. \]
再加上原始性条件 \(\gcd(a,b)=1\)，就得到关键计数公式
\[ G(n)=\#\{(a,b):\ a\ge 2b>0,\ \gcd(a,b)=1,\ Q(a,b)=n\}. \]
模数 \(10^9+9\) 是素数，而且在这个有限域里 \(5\) 有平方根，方程 \(t^2-t-1=0\) 也有两个根 \(\varphi,\psi\)，并满足
\[ \varphi\psi=-1. \]
因此 Binet 公式在模运算环境中同样成立：
\[ F_n=\frac{\varphi^n-\psi^n}{\sqrt 5}. \]
定义
\[ P_w(L)= \sum_{\substack{a\ge 2b>0\\ \gcd(a,b)=1\\ Q(a,b)\le L}} w^{Q(a,b)}. \]
那么原题就化为
\[ \sum_{n\le L} F_n G(n) = \frac{P_\varphi(L)-P_\psi(L)}{\sqrt 5} \pmod{10^9+9}. \]
二次型 \(Q\) 是二次齐次的：
\[ Q(ga,gb)=g^2Q(a,b). \]
如果先忽略 \(\gcd(a,b)=1\)，写成
\[ A_w(L)= \sum_{\substack{a\ge 2b>0\\ Q(a,b)\le L}} w^{Q(a,b)}, \]
那么 Möbius 反演给出
\[ P_w(L)= \sum_{g\le \sqrt L} \mu(g)\, A_{w^{g^2}}\!\left(\left\lfloor \frac{L}{g^2}\right\rfloor\right). \]
也就是说，所有带公因子 \(g\) 的表示都会被统一缩放成 \(g^2\)，然后通过包含-排除把它们精确剔除。
真正让程序高效的恒等式是
\[ 4Q(a,b)=(2a-b)^2-5b^2. \]
令
\[ u=2a-b,\qquad v=b. \]
由 \(a\ge 2b>0\) 可得 \(u\ge 3v>0\)，同时 \(u\equiv v \pmod 2\)。因此只会出现两种奇偶分支。
若 \(u=2m,\ v=2t\)，则
\[ Q(a,b)=m^2-5t^2, \qquad m\ge 3t, \qquad t\ge 1. \]
若 \(u=2m+1,\ v=2t+1\)，则
\[ Q(a,b)=m(m+1)-5t(t+1)-1, \qquad m\ge 3t+1, \qquad t\ge 0. \]
于是 \(A_w(L)\) 分裂成两个一维区间和：
\[ \sum_{t\ge 1} \sum_{m=3t}^{\lfloor \sqrt{L+5t^2}\rfloor} w^{m^2-5t^2}, \]
\[ \sum_{t\ge 0} \sum_{m=3t+1}^{\left\lfloor(\sqrt{4L+20t^2+20t+5}-1)/2\right\rfloor} w^{m(m+1)-5t(t+1)-1}. \]
因为 \(11\equiv 1 \pmod 5\)，所以 \(x^2\equiv x+1 \pmod{11}\) 恰好有两个解：\(x\equiv 4\) 与 \(x\equiv 8\)。因此 \(G(11)=2\)。
而由二次型给出的约化原始表示正好也是两个：
\[ Q(4,1)=16-4-1=11, \qquad Q(5,2)=25-10-4=11. \]
\((4,1)\) 落在奇分支中，因为 \((u,v)=(7,1)\)，所以 \((m,t)=(3,0)\)，并且
\[ m(m+1)-5t(t+1)-1=3\cdot 4-0-1=11. \]
\((5,2)\) 落在偶分支中，因为 \((u,v)=(8,2)\)，所以 \((m,t)=(4,1)\)，并且
\[ m^2-5t^2=16-5=11. \]
这个小例子很好地说明了两件事：为什么 \(G(n)\) 正好等于约化原始表示的个数，以及为什么程序必须同时处理两个奇偶分支。
C++、Python 和 Java 的实现都在模 \(10^9+9\) 下工作。首先它们会验证所选常数确实满足 \(\sqrt 5^2=5\)、\(\varphi^2=\varphi+1\)、\(\psi^2=\psi+1\) 以及 \(\varphi\psi=-1\)。然后在小范围内比较三种完全不同的描述：直接暴力枚举同余方程的解、利用素因子结构得到的 \(G(n)\) 公式、以及由二次型得到的约化原始对计数。最后还会重新计算题目给出的 \(L=10^3\) 样例值。
对固定权重 \(w\)，实现分别处理偶分支和奇分支来计算 \(A_w(L)\)。它不会每次都重新计算 \(w^{m^2}\) 或 \(w^{m(m+1)}\)，而是利用递推式
\[ w^{(m+1)^2}=w^{m^2}w^{2m+1}, \qquad w^{(m+1)(m+2)}=w^{m(m+1)}w^{2m+2} \]
逐步更新幂值。随着 \(t\) 递增，合法的 \(m\) 区间整体向右移动。实现维护一个滑动窗口和：当上界变大时把新项加入窗口，当下界前进时把过期项移出窗口，因此每个允许的幂项只会进入一次、离开一次。
接着，实现对所有满足 \(\mu(g)\neq 0\) 且 \(g\le \sqrt L\) 的 \(g\) 进行扫描，在缩放后的上界 \(\lfloor L/g^2\rfloor\) 上调用前面的求和过程，并按 Möbius 符号做加减。实现还会预先生成 \(\varphi^{g^2}\) 与 \(\varphi^{-g^2}\) 两张表。由于
\[ \psi=-\varphi^{-1}, \]
所以 \(\psi^{g^2}\) 与 \(\varphi^{-g^2}\) 只差一个由 \(g\) 奇偶决定的符号，这样 \(\psi\) 分支几乎不需要额外结构。最后用 \(\varphi\)-加权和减去 \(\psi\)-加权和，再乘上 \(1/\sqrt 5\) 就得到答案。C++ 与 Java 版本还可以把 Möbius 区间分配给多个线程；Python 版本则既支持串行，也支持多进程。
Möbius 数组以及 \(\varphi^{g^2}\)、\(\varphi^{-g^2}\) 两张幂表的规模都是 \(O(\sqrt L)\)，所以内存复杂度是 \(O(\sqrt L)\)。
对固定的 \(g\)，缩放后的上界为 \(L/g^2\)，两条滑动窗口分支合起来需要 \(O(\sqrt{L/g^2})=O(\sqrt L/g)\) 时间。对所有 \(g\le \sqrt L\) 求和得到
\[ O\!\left(\sum_{g\le \sqrt L}\frac{\sqrt L}{g}\right) =O(\sqrt L\log L). \]
这正是算法能够处理 \(L=10^{14}\) 的原因：它既不遍历所有 \(n\le L\)，也不逐个枚举所有原始表示。
Нужно вычислить сумму
\[ \sum_{n=1}^{L} F_n G(n)\pmod{10^9+9}, \qquad L=10^{14}, \]
где \(F_n\) обозначает числа Фибоначчи, а \(G(n)\) равно числу классов вычетов \(x \pmod n\), удовлетворяющих сравнению
\[ x^2 \equiv x+1 \pmod n. \]
Для проверки дано значение
\[ \sum_{n=1}^{10^3} F_n G(n)\equiv 190950976 \pmod{10^9+9}. \]
Перебирать все \(n\) до \(10^{14}\) невозможно. Поэтому решение сначала описывает \(G(n)\) через локальный анализ по простым степеням, затем заменяет веса Фибоначчи экспоненциальными весами через формулу Бине, а после этого сводит задачу к подсчету значений бинарной квадратичной формы с помощью обращения Мёбиуса и скользящих окон.
Исходное сравнение эквивалентно
\[ x^2-x-1 \equiv 0 \pmod n, \]
а его дискриминант равен \(5\). Поэтому локальное поведение целиком определяется тем, является ли \(5\) квадратом по модулю простого числа.
Для \(2^e\) решений нет, то есть \(G(2^e)=0\). Для \(5\) существует ровно одно решение \(x\equiv 3 \pmod 5\), но на модуль \(25\) оно не поднимается, поэтому
\[ G(5)=1, \qquad G(5^e)=0 \ \text{ при } e\ge 2. \]
Пусть теперь \(p\neq 5\) - нечётное простое. Решения по модулю \(p\) существуют тогда и только тогда, когда \(5\) является квадратичным вычетом по модулю \(p\). По закону квадратичной взаимности это эквивалентно условию
\[ p\equiv 1,4 \pmod 5. \]
Тогда по модулю \(p\) есть два различных корня, производная \(2x-1\) в них не обращается в нуль, и лемма Гензеля поднимает каждый корень единственным образом на любое \(p^e\). Если же \(p\equiv 2,3 \pmod 5\), решений нет ни на одной степени \(p\). Следовательно,
\[ G(p^e)= \begin{cases} 2, & p\equiv 1,4 \pmod 5,\\ 0, & p\equiv 2,3 \pmod 5, \end{cases} \qquad (p\neq 5,\ p \text{ нечётное простое}). \]
Из китайской теоремы об остатках следует мультипликативность \(G\). Если
\[ n=5^\varepsilon \prod_{i=1}^{k} p_i^{a_i}\prod_{j=1}^{m} q_j^{b_j}, \]
где все \(p_i\equiv 1,4 \pmod 5\), а каждое \(q_j\) либо равно \(2\), либо удовлетворяет \(q_j\equiv 2,3 \pmod 5\), то \(G(n)=0\), кроме случая \(m=0\) и \(\varepsilon\in\{0,1\}\). В допустимом случае
\[ G(n)=2^k. \]
Далее решение переходит к квадратическому кольцу, порождённому корнем уравнения \(t^2-t-1\). Пусть \(\varphi\) и \(\psi=1-\varphi\) - его корни, так что \(\varphi^2=\varphi+1\). В кольце \(\mathbb Z[\varphi]\) норма элемента \(a-b\varphi\) равна
\[ N(a-b\varphi)=(a-b\varphi)(a-b\psi)=a^2-ab-b^2. \]
Тем самым возникает бинарная квадратичная форма
\[ Q(a,b)=a^2-ab-b^2. \]
Именно те простые, которые дают вклад в \(G(n)\), расщепляются в \(\mathbb Z[\varphi]\). Выбор локального корня для каждой расщеплённой простой степени эквивалентен выбору одного простого множителя над соответствующим рациональным простым. После перемножения этих локальных выборов получается алгебраическое целое с нормой \(n\).
Однако одинаковая норма может быть представлена несколькими эквивалентными способами. Умножение на единицы норму не меняет, поэтому нужно зафиксировать область редукции. В реализации используется условие
\[ a\ge 2b>0. \]
Если дополнительно потребовать \(\gcd(a,b)=1\), то остаются только примитивные представления, и получается ключевая формула
\[ G(n)=\#\{(a,b):\ a\ge 2b>0,\ \gcd(a,b)=1,\ Q(a,b)=n\}. \]
Модуль \(10^9+9\) прост, число \(5\) имеет квадратный корень по этому модулю, а корни \(\varphi,\psi\) уравнения \(t^2-t-1=0\) удовлетворяют
\[ \varphi\psi=-1. \]
Поэтому формула Бине работает и в конечном поле:
\[ F_n=\frac{\varphi^n-\psi^n}{\sqrt 5}. \]
Определим
\[ P_w(L)= \sum_{\substack{a\ge 2b>0\\ \gcd(a,b)=1\\ Q(a,b)\le L}} w^{Q(a,b)}. \]
Тогда исходная сумма принимает вид
\[ \sum_{n\le L} F_n G(n) = \frac{P_\varphi(L)-P_\psi(L)}{\sqrt 5} \pmod{10^9+9}. \]
Форма \(Q\) однородна степени два:
\[ Q(ga,gb)=g^2Q(a,b). \]
Если отбросить условие \(\gcd(a,b)=1\) и ввести
\[ A_w(L)= \sum_{\substack{a\ge 2b>0\\ Q(a,b)\le L}} w^{Q(a,b)}, \]
то обращение Мёбиуса даёт
\[ P_w(L)= \sum_{g\le \sqrt L} \mu(g)\, A_{w^{g^2}}\!\left(\left\lfloor \frac{L}{g^2}\right\rfloor\right). \]
Именно так из общего подсчёта выделяются только примитивные представления.
Ключевое тождество имеет вид
\[ 4Q(a,b)=(2a-b)^2-5b^2. \]
Положим
\[ u=2a-b,\qquad v=b. \]
Из условия \(a\ge 2b>0\) следует \(u\ge 3v>0\), а кроме того \(u\equiv v \pmod 2\). Значит, остаются ровно две ветви.
Если \(u=2m\), \(v=2t\), то
\[ Q(a,b)=m^2-5t^2, \qquad m\ge 3t, \qquad t\ge 1. \]
Если \(u=2m+1\), \(v=2t+1\), то
\[ Q(a,b)=m(m+1)-5t(t+1)-1, \qquad m\ge 3t+1, \qquad t\ge 0. \]
Следовательно, сумма \(A_w(L)\) распадается на две одномерные оконные суммы:
\[ \sum_{t\ge 1} \sum_{m=3t}^{\lfloor \sqrt{L+5t^2}\rfloor} w^{m^2-5t^2}, \]
\[ \sum_{t\ge 0} \sum_{m=3t+1}^{\left\lfloor(\sqrt{4L+20t^2+20t+5}-1)/2\right\rfloor} w^{m(m+1)-5t(t+1)-1}. \]
Поскольку \(11\equiv 1 \pmod 5\), сравнение \(x^2\equiv x+1 \pmod{11}\) имеет ровно два решения: \(x\equiv 4\) и \(x\equiv 8\). Значит, \(G(11)=2\).
Приведённые примитивные представления числа \(11\) формой \(Q(a,b)\) тоже ровно два:
\[ Q(4,1)=16-4-1=11, \qquad Q(5,2)=25-10-4=11. \]
Пара \((4,1)\) попадает в нечётную ветвь: \((u,v)=(7,1)\), поэтому \((m,t)=(3,0)\), и
\[ m(m+1)-5t(t+1)-1=3\cdot 4-0-1=11. \]
Пара \((5,2)\) попадает в чётную ветвь: \((u,v)=(8,2)\), поэтому \((m,t)=(4,1)\), и
\[ m^2-5t^2=16-5=11. \]
Этот пример показывает сразу две вещи: почему число представлений совпадает с \(G(n)\) и почему в программе нужны обе ветви по чётности.
Реализации на C++, Python и Java полностью работают по модулю \(10^9+9\). Сначала они проверяют, что выбранные константы действительно ведут себя как \(\sqrt 5\), \(\varphi\) и \(\psi\), то есть удовлетворяют соотношениям \(\sqrt 5^2=5\), \(\varphi^2=\varphi+1\), \(\psi^2=\psi+1\) и \(\varphi\psi=-1\). Затем на малых значениях сравниваются три независимых описания задачи: прямой перебор решений сравнения, формула для \(G(n)\) через простые множители и подсчёт приведённых примитивных пар для квадратичной формы. После этого воспроизводится опубликованный контрольный пример при \(L=10^3\).
Для фиксированного веса \(w\) реализация вычисляет \(A_w(L)\), отдельно проходя по двум ветвям чётности. Значения \(w^{m^2}\) и \(w^{m(m+1)}\) не пересчитываются с нуля; вместо этого используются рекуррентные переходы
\[ w^{(m+1)^2}=w^{m^2}w^{2m+1}, \qquad w^{(m+1)(m+2)}=w^{m(m+1)}w^{2m+2}. \]
Когда \(t\) растёт, допустимый интервал для \(m\) сдвигается вправо. Поэтому реализация хранит текущую оконную сумму: новые члены добавляются при увеличении верхней границы, а устаревшие удаляются при движении нижней границы. Каждый допустимый член входит в окно один раз и выходит из него один раз.
Далее реализация проходит по всем \(g\le \sqrt L\) с \(\mu(g)\neq 0\), вызывает предыдущий этап при масштабе \(\lfloor L/g^2\rfloor\) и складывает вклад с соответствующим знаком Мёбиуса. Заранее вычисляются таблицы \(\varphi^{g^2}\) и \(\varphi^{-g^2}\). Этого достаточно и для ветви \(\psi\), потому что
\[ \psi=-\varphi^{-1}, \]
а значит, \(\psi^{g^2}\) отличается от \(\varphi^{-g^2}\) только знаком, зависящим от чётности \(g\). В конце сумма для \(\psi\) вычитается из суммы для \(\varphi\), и результат умножается на \(1/\sqrt 5\). В версиях C++ и Java диапазон значений \(g\) можно разделить между потоками; в Python та же математика выполняется либо последовательно, либо через процессы.
Массив значений функции Мёбиуса и таблицы \(\varphi^{g^2}\), \(\varphi^{-g^2}\) имеют размер \(O(\sqrt L)\), поэтому память также равна \(O(\sqrt L)\).
Для фиксированного \(g\) масштабированный предел равен \(L/g^2\), а обе оконные ветви вместе стоят \(O(\sqrt{L/g^2})=O(\sqrt L/g)\). Суммирование по всем \(g\le \sqrt L\) даёт
\[ O\!\left(\sum_{g\le \sqrt L}\frac{\sqrt L}{g}\right) =O(\sqrt L\log L). \]
Именно поэтому метод справляется с \(L=10^{14}\): он не перебирает все \(n\le L\) и не перечисляет примитивные представления по одному.
المطلوب هو حساب المجموع
\[ \sum_{n=1}^{L} F_n G(n)\pmod{10^9+9}, \qquad L=10^{14}, \]
حيث تمثل \(F_n\) أعداد فيبوناتشي، وتمثل \(G(n)\) عدد فئات البواقي \(x \pmod n\) التي تحقق
\[ x^2 \equiv x+1 \pmod n. \]
وقيمة التحقق المنشورة هي
\[ \sum_{n=1}^{10^3} F_n G(n)\equiv 190950976 \pmod{10^9+9}. \]
من المستحيل عمليًا جمع الحدود مباشرة حتى \(10^{14}\). لذلك يعيد الحل بناء \(G(n)\) أولًا من التحليل المحلي على قوى الأعداد الأولية، ثم يحول وزن فيبوناتشي إلى أوزان أسية بواسطة صيغة بينيه، ثم يحسب المجموع الناتج عبر شكل تربيعي ثنائي وعكس موبيوس ونوافذ منزلقة.
المقارنة الأصلية تكافئ
\[ x^2-x-1 \equiv 0 \pmod n, \]
ومميزها هو \(5\). لهذا فإن البنية المحلية كلها تتحكم فيها خاصية كون \(5\) بقايا تربيعية أو لا.
بالنسبة إلى \(2^e\) لا توجد حلول، ومن ثم \(G(2^e)=0\). أما modulo \(5\) فهناك حل وحيد هو \(x\equiv 3 \pmod 5\)، لكنه لا يرتفع إلى modulo \(25\)، ولذلك
\[ G(5)=1, \qquad G(5^e)=0 \ \text{for } e\ge 2. \]
إذا كان \(p\neq 5\) عددًا أوليًا فرديًا، فإن وجود حلول modulo \(p\) يكافئ كون \(5\) بقايا تربيعية modulo \(p\). وبحسب قانون التبادل التربيعي يحدث هذا بالضبط عندما
\[ p\equiv 1,4 \pmod 5. \]
في هذه الحالة توجد جذران بسيطان modulo \(p\)، والمشتقة \(2x-1\) غير منعدمة عندهما، لذا يضمن لمّ هنزل رفع كل جذر على نحو وحيد إلى كل \(p^e\). أما إذا كان \(p\equiv 2,3 \pmod 5\) فلا توجد حلول على أي قوة من قوى \(p\). وبالتالي
\[ G(p^e)= \begin{cases} 2, & p\equiv 1,4 \pmod 5,\\ 0, & p\equiv 2,3 \pmod 5, \end{cases} \qquad (p\neq 5,\ p \text{ odd prime}). \]
وباستخدام مبرهنة البواقي الصينية نستنتج أن \(G\) دالة ضربية. فإذا كتبنا
\[ n=5^\varepsilon \prod_{i=1}^{k} p_i^{a_i}\prod_{j=1}^{m} q_j^{b_j}, \]
حيث كل \(p_i\equiv 1,4 \pmod 5\)، وكل \(q_j\) إما يساوي \(2\) أو يحقق \(q_j\equiv 2,3 \pmod 5\)، فإن \(G(n)=0\) إلا إذا كان \(m=0\) و\(\varepsilon\in\{0,1\}\). وفي الحالة الباقية نحصل على
\[ G(n)=2^k. \]
الخطوة التالية هي الانتقال إلى الحلقة التربيعية المتولدة من جذر المعادلة \(t^2-t-1\). إذا كانت \(\varphi\) و\(\psi=1-\varphi\) هما الجذران، فإن \(\varphi^2=\varphi+1\). في الحلقة \(\mathbb Z[\varphi]\) يكون معيار العنصر \(a-b\varphi\) هو
\[ N(a-b\varphi)=(a-b\varphi)(a-b\psi)=a^2-ab-b^2. \]
ومن هنا يظهر الشكل التربيعي الثنائي الأساسي
\[ Q(a,b)=a^2-ab-b^2. \]
الأوليات التي تساهم في \(G(n)\) هي بالضبط الأوليات التي تنشطر في \(\mathbb Z[\varphi]\). واختيار جذر محلي لكل قوة أولية منشطرة يكافئ اختيار عامل أولي واحد فوق ذلك الأولي النسبي. وعند ضرب جميع هذه الاختيارات نحصل على عدد جبري صحيح معياره \(n\).
لكن المعيار وحده لا يحدد تمثيلًا فريدًا، لأن الضرب في الوحدات لا يغير المعيار، ولأن التمثيلات غير البدائية تضيف عوامل مربعة مشتركة. لذلك نختار منطقة اختزال معيارية هي
\[ a\ge 2b>0. \]
ومع شرط البدائية \(\gcd(a,b)=1\) نحصل على العلاقة الأساسية
\[ G(n)=\#\{(a,b):\ a\ge 2b>0,\ \gcd(a,b)=1,\ Q(a,b)=n\}. \]
بما أن \(10^9+9\) عدد أولي، وبما أن \(5\) له جذر تربيعي modulo هذا العدد، وبما أن \(\varphi,\psi\) هما جذرا \(t^2-t-1\) في هذا الحقل وتحققان
\[ \varphi\psi=-1, \]
فإن صيغة بينيه تبقى صحيحة في الحساب المعياري:
\[ F_n=\frac{\varphi^n-\psi^n}{\sqrt 5}. \]
إذا عرفنا
\[ P_w(L)= \sum_{\substack{a\ge 2b>0\\ \gcd(a,b)=1\\ Q(a,b)\le L}} w^{Q(a,b)}, \]
فإن المجموع المطلوب يصبح
\[ \sum_{n\le L} F_n G(n) = \frac{P_\varphi(L)-P_\psi(L)}{\sqrt 5} \pmod{10^9+9}. \]
الشكل \(Q\) متجانس من الدرجة الثانية:
\[ Q(ga,gb)=g^2Q(a,b). \]
إذا حذفنا مؤقتًا شرط \(\gcd(a,b)=1\) وعرّفنا
\[ A_w(L)= \sum_{\substack{a\ge 2b>0\\ Q(a,b)\le L}} w^{Q(a,b)}, \]
فإن عكس موبيوس يعطي
\[ P_w(L)= \sum_{g\le \sqrt L} \mu(g)\, A_{w^{g^2}}\!\left(\left\lfloor \frac{L}{g^2}\right\rfloor\right). \]
وهكذا تُستعاد التمثيلات البدائية بآلية شمول وإقصاء على القاسم المشترك \(g\).
الهوية الحاسمة هي
\[ 4Q(a,b)=(2a-b)^2-5b^2. \]
نضع
\[ u=2a-b,\qquad v=b. \]
ومن الشرط \(a\ge 2b>0\) نحصل على \(u\ge 3v>0\)، كما أن \(u\equiv v \pmod 2\). لذلك لا يبقى إلا فرعان.
إذا كان \(u=2m\) و\(v=2t\)، فإن
\[ Q(a,b)=m^2-5t^2, \qquad m\ge 3t, \qquad t\ge 1. \]
وإذا كان \(u=2m+1\) و\(v=2t+1\)، فإن
\[ Q(a,b)=m(m+1)-5t(t+1)-1, \qquad m\ge 3t+1, \qquad t\ge 0. \]
وبذلك ينقسم \(A_w(L)\) إلى مجموعين أحاديي البعد:
\[ \sum_{t\ge 1} \sum_{m=3t}^{\lfloor \sqrt{L+5t^2}\rfloor} w^{m^2-5t^2}, \]
\[ \sum_{t\ge 0} \sum_{m=3t+1}^{\left\lfloor(\sqrt{4L+20t^2+20t+5}-1)/2\right\rfloor} w^{m(m+1)-5t(t+1)-1}. \]
بما أن \(11\equiv 1 \pmod 5\)، فإن المعادلة \(x^2\equiv x+1 \pmod{11}\) لها حلان بالضبط: \(x\equiv 4\) و\(x\equiv 8\). إذن \(G(11)=2\).
والتمثيلات البدائية المختزلة للعدد \(11\) بواسطة \(Q(a,b)\) هي
\[ Q(4,1)=16-4-1=11, \qquad Q(5,2)=25-10-4=11. \]
الزوج \((4,1)\) يقع في الفرع الفردي، لأن \((u,v)=(7,1)\)، وبالتالي \((m,t)=(3,0)\)، ومن ثم
\[ m(m+1)-5t(t+1)-1=3\cdot 4-0-1=11. \]
أما الزوج \((5,2)\) فيقع في الفرع الزوجي، لأن \((u,v)=(8,2)\)، وبالتالي \((m,t)=(4,1)\)، فنحصل على
\[ m^2-5t^2=16-5=11. \]
يوضح هذا المثال الصغير لماذا يساوي عدد الأزواج \(G(n)\)، ولماذا لا بد من استخدام الفرعين معًا في الحساب النهائي.
تعمل تطبيقات C++ وPython وJava كلها modulo \(10^9+9\). في البداية تتحقق من أن الثوابت المختارة تمثل فعلًا \(\sqrt 5\) و\(\varphi\) و\(\psi\)، أي إن العلاقات \(\sqrt 5^2=5\) و\(\varphi^2=\varphi+1\) و\(\psi^2=\psi+1\) و\(\varphi\psi=-1\) صحيحة. بعد ذلك تقارن بين ثلاث صور للمسألة على قيم صغيرة: العد المباشر لحلول المقارنة، والصيغة المستخرجة من تحليل العوامل الأولية لـ \(G(n)\)، وعدد الأزواج المختزلة البدائية للشكل التربيعي. وأخيرًا تعيد إنتاج قيمة العينة المنشورة عند \(L=10^3\).
لوزن ثابت \(w\)، يحسب التنفيذ \(A_w(L)\) عبر المرور على الفرعين المنفصلين. ولا يعيد كل مرة حساب \(w^{m^2}\) أو \(w^{m(m+1)}\) من الصفر، بل يحدث هاتين السلسلتين ضربياً باستعمال
\[ w^{(m+1)^2}=w^{m^2}w^{2m+1}, \qquad w^{(m+1)(m+2)}=w^{m(m+1)}w^{2m+2}. \]
ومع ازدياد \(t\) تتحرك الفترة المسموح بها لـ \(m\) إلى اليمين. لذلك يحتفظ التنفيذ بمجموع نافذة جارٍ: يضيف الحدود الجديدة عندما يكبر الحد الأعلى، ويحذف الحدود المنتهية عندما يتقدم الحد الأدنى. وبهذا يدخل كل حد مرة واحدة ويخرج مرة واحدة.
بعد ذلك يمر التنفيذ على كل \(g\le \sqrt L\) بحيث \(\mu(g)\neq 0\)، ويستدعي مرحلة المجموع السابقة على الحد المصغر \(\lfloor L/g^2\rfloor\)، ثم يجمع أو يطرح وفق إشارة موبيوس. كما يسبق له أن يحسب جدولي \(\varphi^{g^2}\) و\(\varphi^{-g^2}\). وهذا يكفي أيضًا لفرع \(\psi\)، لأن
\[ \psi=-\varphi^{-1}, \]
ومن ثم لا تختلف \(\psi^{g^2}\) عن \(\varphi^{-g^2}\) إلا بإشارة تعتمد على فردية \(g\). وفي النهاية يطرح المجموع الموزون بـ \(\psi\) من المجموع الموزون بـ \(\varphi\)، ثم يضرب في \(1/\sqrt 5\). ويمكن لإصداري C++ وJava توزيع مجال قيم \(g\) على عدة خيوط، بينما يدعم إصدار Python الحساب نفسه بصورة تسلسلية أو عبر عمليات متعددة.
مصفوفة قيم موبيوس وجدولا \(\varphi^{g^2}\) و\(\varphi^{-g^2}\) جميعها بحجم \(O(\sqrt L)\)، ولذلك فإن استهلاك الذاكرة يساوي \(O(\sqrt L)\).
بالنسبة إلى \(g\) ثابت، يكون الحد المصغر \(L/g^2\)، وتكلفة فرعي النوافذ المنزلقـة معًا هي \(O(\sqrt{L/g^2})=O(\sqrt L/g)\). وعند الجمع على جميع \(g\le \sqrt L\) نحصل على
\[ O\!\left(\sum_{g\le \sqrt L}\frac{\sqrt L}{g}\right) =O(\sqrt L\log L). \]
ولهذا يمكن للطريقة أن تتعامل مع \(L=10^{14}\): فهي لا تمر على جميع \(n\le L\) واحدًا واحدًا، ولا تعدّ كل التمثيلات البدائية على حدة.