The sequence defines rational points \(P_n=(x_n,y_n)\) on one fixed hyperbola. If
$$x_n=\frac{a_n}{b_n},\qquad y_n=\frac{c_n}{d_n}$$
are written in lowest terms with positive denominators, the required value is the checksum
$$C_n \equiv a_n+b_n+c_n+d_n \pmod{10^9+7}.$$
The hard part is that the target index is enormous, so a direct rational simulation of the recurrence is useless. The implementations instead extract a closed form for the point coordinates and evaluate that form purely modulo \(10^9+7\).
The implementations begin with the auxiliary sequence
$$u_1=100,\qquad u_2=-\frac{75}{2},\qquad u_n=\frac{25u_{n-2}}{u_{n-1}}\qquad (n\ge 3).$$
The point coordinates are then reconstructed by
$$x_n=\frac{3u_n^2+2500}{25u_n},\qquad y_n=\frac{4u_n^2-1875}{25u_n}.$$
These formulas immediately yield two useful linear combinations:
$$3x_n+4y_n=u_n,\qquad 4x_n-3y_n=\frac{625}{u_n}.$$
Multiplying them gives
$$\boxed{(3x_n+4y_n)(4x_n-3y_n)=625,}$$
so every \(P_n\) lies on the same hyperbola. The sequence \(u_n\) is therefore a rational parameter of that curve.
Set
$$q_n=\frac{u_n}{25}.$$
Then the recurrence simplifies to
$$q_1=4,\qquad q_2=-\frac{3}{2},\qquad q_n=\frac{q_{n-2}}{q_{n-1}}\qquad (n\ge 3).$$
This normalized form is the key observation: only the primes \(2\) and \(3\) appear, so the whole problem becomes a recurrence on exponents and signs.
Write each term as
$$q_n=\varepsilon_n\,2^{a_n}3^{b_n},\qquad \varepsilon_n\in\{-1,+1\},$$
where negative exponents simply mean factors in the denominator. Taking \(2\)-adic and \(3\)-adic valuations in
$$q_n=\frac{q_{n-2}}{q_{n-1}}$$
gives the linear recurrences
$$a_n=a_{n-2}-a_{n-1},\qquad b_n=b_{n-2}-b_{n-1},$$
with initial values
$$a_1=2,\ a_2=-1,\qquad b_1=0,\ b_2=1.$$
Now define
$$A_n=(-1)^{n+1}a_n,\qquad B_n=(-1)^n b_n.$$
Then both sequences satisfy the ordinary Fibonacci recurrence
$$A_n=A_{n-1}+A_{n-2},\qquad B_n=B_{n-1}+B_{n-2}.$$
The initial values identify them uniquely as
$$A_n=L_{n-1},\qquad B_n=F_{n-1},$$
where \(F_k\) and \(L_k\) are the Fibonacci and Lucas numbers with
$$F_0=0,\ F_1=1,\qquad L_0=2,\ L_1=1.$$
Therefore
$$a_n=(-1)^{n+1}L_{n-1},\qquad b_n=(-1)^nF_{n-1}.$$
The sign follows the same recurrence: from \(q_n=q_{n-2}/q_{n-1}\) we get
$$\varepsilon_n=\varepsilon_{n-2}\varepsilon_{n-1},\qquad \varepsilon_1=+1,\ \varepsilon_2=-1,$$
so
$$\varepsilon_n=(-1)^{F_{n-1}}.$$
Let \(k=n-1\) and define
$$\sigma=(-1)^{F_k}.$$
Then the normalized recurrence has the exact solution
$$q_n=\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n \text{ odd},\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n \text{ even}. \end{cases}$$
Multiplying by \(25\) gives the auxiliary parameter
$$u_n=25q_n=25\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n \text{ odd},\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n \text{ even}. \end{cases}$$
To make the coordinate formulas symmetric, define \((\alpha,\beta)\) by parity:
$$n \text{ odd}: \alpha=2^{L_k},\ \beta=3^{F_k},\qquad n \text{ even}: \alpha=3^{F_k},\ \beta=2^{L_k}.$$
Then in both cases \(u_n=25\sigma\alpha/\beta\), and substitution into the coordinate formulas yields
$$\boxed{x_n=\sigma\frac{3\alpha^2+4\beta^2}{\alpha\beta},\qquad y_n=\sigma\frac{4\alpha^2-3\beta^2}{\alpha\beta}.}$$
This is the exact algebraic form used by the modular solver.
The checksum uses reduced fractions, so we must know the common factors of each raw numerator with the raw denominator \(\alpha\beta\).
For odd \(n\), \(\alpha\) is a power of \(2\) and \(\beta\) is a power of \(3\). When \(n\ge 3\), \(\alpha\) is divisible by \(8\) and \(\beta\) is divisible by \(3\). Then:
$$3\alpha^2+4\beta^2\ \text{is divisible by}\ 12,$$
but after dividing by \(12\) the result is odd and not divisible by \(3\), so no larger common factor with \(\alpha\beta\) remains. By contrast,
$$4\alpha^2-3\beta^2\equiv 1 \pmod 3,\qquad 4\alpha^2-3\beta^2\equiv 5 \pmod 8,$$
so it is coprime to \(\alpha\beta\). Hence
$$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=\begin{cases}4,&n=1,\\12,&n\ge 3\text{ odd},\end{cases}\qquad \gcd(4\alpha^2-3\beta^2,\alpha\beta)=1\ \text{for odd }n.$$
For even \(n\), the roles of powers of \(2\) and \(3\) are reversed. Then \(3\alpha^2+4\beta^2\) is odd and congruent to \(1 \pmod 3\), so it is already reduced. The other numerator has exactly one factor \(3\), and for \(n\ge 4\) exactly two factors of \(2\):
$$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=1\ \text{for even }n,$$
$$\gcd(4\alpha^2-3\beta^2,\alpha\beta)=\begin{cases}6,&n=2,\\12,&n\ge 4\text{ even}.\end{cases}$$
These fixed divisors are exactly the small reductions used before the checksum is formed.
This index is one of the implementation checkpoints. Here \(k=6\), so
$$F_6=8,\qquad L_6=18,\qquad \sigma=(-1)^8=1.$$
Because \(7\) is odd, we take
$$\alpha=2^{18}=262144,\qquad \beta=3^8=6561.$$
Then
$$x_7=\frac{3\alpha^2+4\beta^2}{\alpha\beta}=\frac{206330617092}{1719926784}=\frac{17194218091}{143327232},$$
where the reduction factor is \(12\), and
$$y_7=\frac{4\alpha^2-3\beta^2}{\alpha\beta}=\frac{274748766781}{1719926784},$$
which is already reduced. These are exactly the rational checkpoint values used to verify the formula.
Let \(M=10^9+7\). Since \(M\) is prime and neither \(2\) nor \(3\) is divisible by \(M\), Fermat's little theorem allows exponent reduction modulo
$$M-1=10^9+6.$$
So the implementation computes \(F_k\) and \(F_{k+1}\) modulo \(M-1\), then derives
$$L_k=2F_{k+1}-F_k.$$
The Fibonacci pair is obtained by fast doubling:
$$F_{2m}=F_m(2F_{m+1}-F_m),\qquad F_{2m+1}=F_m^2+F_{m+1}^2.$$
Once \(F_k\) and \(L_k\) are known modulo \(M-1\), the powers \(2^{L_k}\) and \(3^{F_k}\) are computed modulo \(M\). Division by \(4\), \(6\), or \(12\) is replaced by multiplication with modular inverses:
$$a^{-1}\equiv a^{M-2}\pmod M.$$
The sign is also cheap: Fibonacci parity has period \(3\), so \(F_k\) is even exactly when \(k\equiv 0\pmod 3\). Therefore \(\sigma=+1\) in that case and \(\sigma=-1\) otherwise.
The C++, Python, and Java implementations all follow the same pipeline. They compute \(k=n-1\), obtain \(F_k\) and \(F_{k+1}\) by fast doubling modulo \(10^9+6\), recover \(L_k\), choose the correct parity branch for \((\alpha,\beta)\), form the two raw numerators and the common raw denominator modulo \(10^9+7\), divide by the known reduction factors with modular inverses, and finally add the four reduced pieces. The C++ implementation also checks the formula against exact rational arithmetic for small indices, which confirms that the modular shortcut is mathematically exact.
Fast doubling computes Fibonacci data in \(O(\log n)\) time. Modular exponentiation also costs \(O(\log M)\), which is constant-sized compared with the growth of \(n\). The overall solver therefore runs in \(O(\log n)\) time and \(O(1)\) memory. That is why an index as large as \(11^{14}\) is completely feasible.
Die Folge definiert rationale Punkte \(P_n=(x_n,y_n)\) auf einer festen Hyperbel. Werden
$$x_n=\frac{a_n}{b_n},\qquad y_n=\frac{c_n}{d_n}$$
vollständig gekürzt und mit positiven Nennern geschrieben, so ist gesucht
$$C_n \equiv a_n+b_n+c_n+d_n \pmod{10^9+7}.$$
Der Zielindex ist extrem groß, daher ist eine direkte Simulation der rationalen Rekursion unbrauchbar. Die Lösung leitet stattdessen eine geschlossene Form für die Koordinaten her und wertet diese direkt modulo \(10^9+7\) aus.
Die Implementierungen starten mit der Hilfsfolge
$$u_1=100,\qquad u_2=-\frac{75}{2},\qquad u_n=\frac{25u_{n-2}}{u_{n-1}}\qquad (n\ge 3).$$
Daraus werden die Koordinaten rekonstruiert durch
$$x_n=\frac{3u_n^2+2500}{25u_n},\qquad y_n=\frac{4u_n^2-1875}{25u_n}.$$
Diese Darstellung liefert sofort zwei lineare Kombinationen:
$$3x_n+4y_n=u_n,\qquad 4x_n-3y_n=\frac{625}{u_n}.$$
Multiplikation ergibt
$$\boxed{(3x_n+4y_n)(4x_n-3y_n)=625,}$$
also liegen alle Punkte auf derselben Hyperbel. Die Folge \(u_n\) ist damit ein rationaler Parameter dieser Kurve.
Setze
$$q_n=\frac{u_n}{25}.$$
Dann vereinfacht sich die Rekursion zu
$$q_1=4,\qquad q_2=-\frac{3}{2},\qquad q_n=\frac{q_{n-2}}{q_{n-1}}\qquad (n\ge 3).$$
In dieser normalisierten Form sieht man sofort, dass nur die Primzahlen \(2\) und \(3\) auftreten. Das Problem wird damit zu einer Rekursion auf Exponenten und Vorzeichen.
Schreibe
$$q_n=\varepsilon_n\,2^{a_n}3^{b_n},\qquad \varepsilon_n\in\{-1,+1\},$$
wobei negative Exponenten Faktoren im Nenner bedeuten. Aus
$$q_n=\frac{q_{n-2}}{q_{n-1}}$$
folgt für die \(2\)- und \(3\)-adischen Bewertungen
$$a_n=a_{n-2}-a_{n-1},\qquad b_n=b_{n-2}-b_{n-1},$$
mit Anfangswerten
$$a_1=2,\ a_2=-1,\qquad b_1=0,\ b_2=1.$$
Definiert man nun
$$A_n=(-1)^{n+1}a_n,\qquad B_n=(-1)^n b_n,$$
dann erfüllen beide Folgen die gewöhnliche Fibonacci-Rekursion
$$A_n=A_{n-1}+A_{n-2},\qquad B_n=B_{n-1}+B_{n-2}.$$
Die Anfangswerte identifizieren sie eindeutig als
$$A_n=L_{n-1},\qquad B_n=F_{n-1},$$
wobei
$$F_0=0,\ F_1=1,\qquad L_0=2,\ L_1=1.$$
Damit gilt
$$a_n=(-1)^{n+1}L_{n-1},\qquad b_n=(-1)^nF_{n-1}.$$
Auch das Vorzeichen folgt einer linearen Struktur. Aus \(q_n=q_{n-2}/q_{n-1}\) erhält man
$$\varepsilon_n=\varepsilon_{n-2}\varepsilon_{n-1},\qquad \varepsilon_1=+1,\ \varepsilon_2=-1,$$
und daher
$$\varepsilon_n=(-1)^{F_{n-1}}.$$
Setze \(k=n-1\) und
$$\sigma=(-1)^{F_k}.$$
Dann besitzt die normalisierte Folge die exakte Darstellung
$$q_n=\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n \text{ ungerade},\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n \text{ gerade}. \end{cases}$$
Somit ist
$$u_n=25q_n=25\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n \text{ ungerade},\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n \text{ gerade}. \end{cases}$$
Für eine symmetrische Schreibweise definiert man \((\alpha,\beta)\) abhängig von der Parität:
$$n \text{ ungerade}: \alpha=2^{L_k},\ \beta=3^{F_k},\qquad n \text{ gerade}: \alpha=3^{F_k},\ \beta=2^{L_k}.$$
Dann gilt in beiden Fällen \(u_n=25\sigma\alpha/\beta\), und durch Einsetzen folgt
$$\boxed{x_n=\sigma\frac{3\alpha^2+4\beta^2}{\alpha\beta},\qquad y_n=\sigma\frac{4\alpha^2-3\beta^2}{\alpha\beta}.}$$
Genau diese Formeln werden im modularen Teil der Lösung verwendet.
Für die Prüfsumme braucht man die vollständig gekürzten Brüche. Deshalb muss der größte gemeinsame Teiler jedes rohen Zählers mit dem rohen Nenner \(\alpha\beta\) bekannt sein.
Für ungerades \(n\) ist \(\alpha\) eine Zweierpotenz und \(\beta\) eine Dreierpotenz. Für \(n\ge 3\) ist \(\alpha\) durch \(8\) und \(\beta\) durch \(3\) teilbar. Dann ist
$$3\alpha^2+4\beta^2\ \text{durch}\ 12\ \text{teilbar},$$
aber nach Division durch \(12\) bleibt weder ein weiterer Faktor \(2\) noch ein weiterer Faktor \(3\) übrig. Dagegen gilt
$$4\alpha^2-3\beta^2\equiv 1 \pmod 3,\qquad 4\alpha^2-3\beta^2\equiv 5 \pmod 8,$$
also ist dieser Zähler teilerfremd zu \(\alpha\beta\). Damit
$$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=\begin{cases}4,&n=1,\\12,&n\ge 3\text{ ungerade},\end{cases}\qquad \gcd(4\alpha^2-3\beta^2,\alpha\beta)=1\ \text{für ungerades }n.$$
Für gerades \(n\) vertauschen sich die Rollen von Zweier- und Dreierpotenzen. Dann ist \(3\alpha^2+4\beta^2\) ungerade und kongruent zu \(1 \pmod 3\), also bereits gekürzt. Der zweite Zähler besitzt genau einen Faktor \(3\) und für \(n\ge 4\) genau zwei Faktoren \(2\):
$$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=1\ \text{für gerades }n,$$
$$\gcd(4\alpha^2-3\beta^2,\alpha\beta)=\begin{cases}6,&n=2,\\12,&n\ge 4\text{ gerade}.\end{cases}$$
Genau diese festen Reduktionsfaktoren benutzt die Implementierung vor der Bildung der Prüfsumme.
Dieser Index ist einer der Kontrollpunkte der Implementierung. Es ist \(k=6\), also
$$F_6=8,\qquad L_6=18,\qquad \sigma=(-1)^8=1.$$
Da \(7\) ungerade ist, wählen wir
$$\alpha=2^{18}=262144,\qquad \beta=3^8=6561.$$
Dann folgt
$$x_7=\frac{3\alpha^2+4\beta^2}{\alpha\beta}=\frac{206330617092}{1719926784}=\frac{17194218091}{143327232},$$
wobei um den Faktor \(12\) gekürzt wird, und
$$y_7=\frac{4\alpha^2-3\beta^2}{\alpha\beta}=\frac{274748766781}{1719926784},$$
was bereits vollständig gekürzt ist. Diese Werte stimmen mit dem exakten Kontrollpunkt überein.
Sei \(M=10^9+7\). Weil \(M\) prim ist und weder \(2\) noch \(3\) durch \(M\) teilbar sind, dürfen Exponenten modulo
$$M-1=10^9+6$$
reduziert werden. Daher berechnet die Implementierung \(F_k\) und \(F_{k+1}\) modulo \(M-1\) und gewinnt daraus
$$L_k=2F_{k+1}-F_k.$$
Das Fibonacci-Paar wird per fast doubling berechnet:
$$F_{2m}=F_m(2F_{m+1}-F_m),\qquad F_{2m+1}=F_m^2+F_{m+1}^2.$$
Sobald \(F_k\) und \(L_k\) modulo \(M-1\) bekannt sind, werden \(2^{L_k}\) und \(3^{F_k}\) modulo \(M\) ausgewertet. Divisionen durch \(4\), \(6\) oder \(12\) werden durch modulare Inverse ersetzt:
$$a^{-1}\equiv a^{M-2}\pmod M.$$
Auch das Vorzeichen ist billig zu bestimmen: Die Parität der Fibonacci-Zahlen hat Periode \(3\), also ist \(F_k\) genau dann gerade, wenn \(k\equiv 0\pmod 3\). Dann ist \(\sigma=+1\), sonst \(\sigma=-1\).
Die C++-, Python- und Java-Implementierungen folgen demselben Ablauf. Zuerst wird \(k=n-1\) berechnet. Danach werden \(F_k\) und \(F_{k+1}\) modulo \(10^9+6\) per fast doubling bestimmt, daraus \(L_k\) rekonstruiert, dann der passende Paritätsfall für \((\alpha,\beta)\) gewählt und die beiden rohen Zähler sowie der gemeinsame rohe Nenner modulo \(10^9+7\) gebildet. Anschließend werden die bekannten Reduktionsfaktoren über modulare Inverse herausgeteilt, und zuletzt werden die vier gekürzten Restklassen addiert. Die C++-Implementierung prüft die Formel zusätzlich für kleine Indizes mit exakter rationaler Arithmetik, was die mathematische Korrektheit der modularen Abkürzung bestätigt.
Fast doubling liefert die Fibonacci-Daten in \(O(\log n)\) Zeit. Die modularen Potenzierungen kosten \(O(\log M)\), also nur konstante Größe im Vergleich zum Wachstum von \(n\). Insgesamt läuft der eigentliche Solver daher in \(O(\log n)\) Zeit und benötigt \(O(1)\) Speicher. Deshalb ist auch ein Index wie \(11^{14}\) problemlos handhabbar.
Dizi, sabit bir hiperbol üzerindeki rasyonel noktaları \(P_n=(x_n,y_n)\) olarak tanımlar. Eğer
$$x_n=\frac{a_n}{b_n},\qquad y_n=\frac{c_n}{d_n}$$
tam sadeleştirilmiş ve paydaları pozitif olacak biçimde yazılırsa, istenen değer şu checksum’dır:
$$C_n \equiv a_n+b_n+c_n+d_n \pmod{10^9+7}.$$
Hedef indis çok büyük olduğu için rasyonel yinelemeyi adım adım yürütmek işe yaramaz. Bunun yerine uygulamalar, koordinatlar için kapalı bir form çıkarıp her şeyi doğrudan \(10^9+7\) modunda hesaplar.
Uygulamalar önce yardımcı diziyi kullanır:
$$u_1=100,\qquad u_2=-\frac{75}{2},\qquad u_n=\frac{25u_{n-2}}{u_{n-1}}\qquad (n\ge 3).$$
Daha sonra nokta koordinatları
$$x_n=\frac{3u_n^2+2500}{25u_n},\qquad y_n=\frac{4u_n^2-1875}{25u_n}$$
formülleriyle elde edilir. Buradan iki önemli doğrusal birleşim çıkar:
$$3x_n+4y_n=u_n,\qquad 4x_n-3y_n=\frac{625}{u_n}.$$
Çarpınca
$$\boxed{(3x_n+4y_n)(4x_n-3y_n)=625,}$$
olur. Yani tüm noktalar aynı hiperbol üzerindedir ve \(u_n\) bu eğrinin rasyonel bir parametresidir.
Şunu tanımlayalım:
$$q_n=\frac{u_n}{25}.$$
O zaman yineleme şu sade biçime iner:
$$q_1=4,\qquad q_2=-\frac{3}{2},\qquad q_n=\frac{q_{n-2}}{q_{n-1}}\qquad (n\ge 3).$$
Bu normalleştirme belirleyicidir; çünkü artık yalnızca \(2\) ve \(3\) asal çarpanları görünür, dolayısıyla asıl yapı üsler ve işaret üzerinde gizlidir.
Her terimi
$$q_n=\varepsilon_n\,2^{a_n}3^{b_n},\qquad \varepsilon_n\in\{-1,+1\},$$
şeklinde yazalım. Negatif üsler ilgili asalın paydada olduğu anlamına gelir. Yinelemede
$$q_n=\frac{q_{n-2}}{q_{n-1}}$$
olduğu için \(2\)-adik ve \(3\)-adik üsler
$$a_n=a_{n-2}-a_{n-1},\qquad b_n=b_{n-2}-b_{n-1}$$
ilişkisini sağlar. Başlangıç değerleri
$$a_1=2,\ a_2=-1,\qquad b_1=0,\ b_2=1$$
olur. Şimdi
$$A_n=(-1)^{n+1}a_n,\qquad B_n=(-1)^n b_n$$
tanımını yaparsak, bu iki dizi sıradan Fibonacci yinelemesine uyar:
$$A_n=A_{n-1}+A_{n-2},\qquad B_n=B_{n-1}+B_{n-2}.$$
Başlangıç değerleri bunları doğrudan
$$A_n=L_{n-1},\qquad B_n=F_{n-1}$$
olarak tanımlar; burada
$$F_0=0,\ F_1=1,\qquad L_0=2,\ L_1=1.$$
Dolayısıyla
$$a_n=(-1)^{n+1}L_{n-1},\qquad b_n=(-1)^nF_{n-1}.$$
İşaret de benzer biçimde çözülür. \(q_n=q_{n-2}/q_{n-1}\) olduğundan
$$\varepsilon_n=\varepsilon_{n-2}\varepsilon_{n-1},\qquad \varepsilon_1=+1,\ \varepsilon_2=-1,$$
ve sonuç olarak
$$\varepsilon_n=(-1)^{F_{n-1}}.$$
\(k=n-1\) ve
$$\sigma=(-1)^{F_k}$$
olsun. O zaman normalize dizi tam olarak
$$q_n=\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n \text{ tek},\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n \text{ çift} \end{cases}$$
şeklindedir. Buradan
$$u_n=25q_n=25\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n \text{ tek},\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n \text{ çift} \end{cases}$$
elde edilir. Koordinat formüllerini simetrik yazmak için \((\alpha,\beta)\) çiftini şöyle seçelim:
$$n \text{ tek}: \alpha=2^{L_k},\ \beta=3^{F_k},\qquad n \text{ çift}: \alpha=3^{F_k},\ \beta=2^{L_k}.$$
Bu durumda her iki paritede de \(u_n=25\sigma\alpha/\beta\) olur ve yerine koyunca
$$\boxed{x_n=\sigma\frac{3\alpha^2+4\beta^2}{\alpha\beta},\qquad y_n=\sigma\frac{4\alpha^2-3\beta^2}{\alpha\beta}}$$
sonucuna ulaşılır. Modüler çözücü tam olarak bu cebirsel biçimi kullanır.
Checksum, sadeleşmiş pay ve paydayı kullandığı için her ham payın \(\alpha\beta\) ile ortak bölenini bilmek gerekir.
Tek \(n\) için \(\alpha\) bir \(2\) kuvveti, \(\beta\) ise bir \(3\) kuvvetidir. \(n\ge 3\) olduğunda \(\alpha\) en az \(8\)’e, \(\beta\) ise \(3\)’e bölünür. Bu durumda
$$3\alpha^2+4\beta^2\ \text{tam olarak}\ 12\ \text{ortak çarpanını taşır},$$
çünkü \(12\)’ye böldükten sonra sonuç ne çift kalır ne de \(3\)’e bölünür. Buna karşılık
$$4\alpha^2-3\beta^2\equiv 1 \pmod 3,\qquad 4\alpha^2-3\beta^2\equiv 5 \pmod 8,$$
olduğundan \(\alpha\beta\) ile aralarında asaldır. Sonuç olarak
$$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=\begin{cases}4,&n=1,\\12,&n\ge 3\text{ tek},\end{cases}\qquad \gcd(4\alpha^2-3\beta^2,\alpha\beta)=1\ \text{tek }n\text{ için}.$$
Çift \(n\) için \(2\) ve \(3\) kuvvetlerinin rolleri tersine döner. Bu kez \(3\alpha^2+4\beta^2\) tek sayıdır ve \(3\) ile de bölünmez; yani zaten sadeleşmiştir. Öteki pay ise tam bir adet \(3\), ayrıca \(n\ge 4\) ise tam iki adet \(2\) içerir:
$$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=1\ \text{çift }n\text{ için},$$
$$\gcd(4\alpha^2-3\beta^2,\alpha\beta)=\begin{cases}6,&n=2,\\12,&n\ge 4\text{ çift}.\end{cases}$$
Uygulamanın checksum’dan önce uyguladığı sabit sadeleştirme çarpanları bunlardır.
Bu indis, uygulamadaki kontrol noktalarından biridir. Burada \(k=6\) olduğundan
$$F_6=8,\qquad L_6=18,\qquad \sigma=(-1)^8=1.$$
\(7\) tek olduğu için
$$\alpha=2^{18}=262144,\qquad \beta=3^8=6561$$
alınır. Böylece
$$x_7=\frac{3\alpha^2+4\beta^2}{\alpha\beta}=\frac{206330617092}{1719926784}=\frac{17194218091}{143327232},$$
yani burada sadeleştirme faktörü \(12\)’dir. Ayrıca
$$y_7=\frac{4\alpha^2-3\beta^2}{\alpha\beta}=\frac{274748766781}{1719926784},$$
ve bu kesir zaten sade haldedir. Böylece doğrulama için kullanılan rasyonel değerler elde edilir.
\(M=10^9+7\) olsun. \(M\) asal olduğu ve \(2\) ile \(3\) bu moda göre sıfır olmadığı için üsler
$$M-1=10^9+6$$
modunda azaltılabilir. Bu yüzden uygulama \(F_k\) ile \(F_{k+1}\) değerlerini \(M-1\) modunda hesaplar ve sonra
$$L_k=2F_{k+1}-F_k$$
bağlantısını kullanır. Fibonacci çifti fast doubling ile elde edilir:
$$F_{2m}=F_m(2F_{m+1}-F_m),\qquad F_{2m+1}=F_m^2+F_{m+1}^2.$$
\(F_k\) ve \(L_k\) bilinince \(2^{L_k}\) ile \(3^{F_k}\) mod \(M\) hesaplanır. \(4\), \(6\) ve \(12\) ile bölmeler ise modüler terslerle yapılır:
$$a^{-1}\equiv a^{M-2}\pmod M.$$
İşaret de ucuzdur: Fibonacci paritesi \(3\) dönemlidir. Yani \(F_k\) ancak ve ancak \(k\equiv 0\pmod 3\) ise çifttir; bu durumda \(\sigma=+1\), aksi halde \(\sigma=-1\).
C++, Python ve Java implementasyonları aynı akışı izler. Önce \(k=n-1\) hesaplanır. Ardından fast doubling ile \(F_k\) ve \(F_{k+1}\) değerleri \(10^9+6\) modunda bulunur, buradan \(L_k\) elde edilir, pariteye göre doğru \((\alpha,\beta)\) kolu seçilir ve iki ham pay ile ortak ham payda \(10^9+7\) modunda oluşturulur. Sonraki adımda bilinen sadeleştirme çarpanları modüler terslerle uygulanır ve en sonda dört sadeleştirilmiş parça toplanır. C++ uygulaması ayrıca küçük indisler için tam rasyonel aritmetik ile karşılaştırma yaparak modüler kısayolun matematiksel olarak tam doğru olduğunu gösterir.
Fast doubling ile Fibonacci verileri \(O(\log n)\) zamanda elde edilir. Modüler üs alma ise \(O(\log M)\) maliyetlidir; bu da \(n\)’in büyümesine göre sabit sayılabilecek bir üst sınırdır. Dolayısıyla ana çözücü toplamda \(O(\log n)\) zamanda ve \(O(1)\) bellekte çalışır. Bu yüzden \(11^{14}\) gibi dev indisler pratik olarak hesaplanabilir.
La sucesión define puntos racionales \(P_n=(x_n,y_n)\) sobre una hipérbola fija. Si
$$x_n=\frac{a_n}{b_n},\qquad y_n=\frac{c_n}{d_n}$$
se escriben en términos reducidos y con denominadores positivos, el valor pedido es
$$C_n \equiv a_n+b_n+c_n+d_n \pmod{10^9+7}.$$
Como el índice objetivo es gigantesco, no sirve simular la recurrencia racional paso a paso. La idea correcta es deducir una fórmula cerrada para las coordenadas y evaluar esa fórmula directamente módulo \(10^9+7\).
Las implementaciones parten de la sucesión auxiliar
$$u_1=100,\qquad u_2=-\frac{75}{2},\qquad u_n=\frac{25u_{n-2}}{u_{n-1}}\qquad (n\ge 3).$$
Luego reconstruyen las coordenadas mediante
$$x_n=\frac{3u_n^2+2500}{25u_n},\qquad y_n=\frac{4u_n^2-1875}{25u_n}.$$
De aquí se obtienen dos combinaciones lineales muy útiles:
$$3x_n+4y_n=u_n,\qquad 4x_n-3y_n=\frac{625}{u_n}.$$
Al multiplicarlas aparece la ecuación
$$\boxed{(3x_n+4y_n)(4x_n-3y_n)=625,}$$
de modo que todos los puntos pertenecen a la misma hipérbola. Así, \(u_n\) actúa como parámetro racional de la curva.
Definimos
$$q_n=\frac{u_n}{25}.$$
Entonces la recurrencia queda
$$q_1=4,\qquad q_2=-\frac{3}{2},\qquad q_n=\frac{q_{n-2}}{q_{n-1}}\qquad (n\ge 3).$$
Esta normalización es crucial: sólo aparecen los primos \(2\) y \(3\), así que la estructura real del problema está en los exponentes y en el signo.
Escribimos cada término como
$$q_n=\varepsilon_n\,2^{a_n}3^{b_n},\qquad \varepsilon_n\in\{-1,+1\},$$
donde exponentes negativos significan factores en el denominador. Aplicando valuaciones \(2\)-ádicas y \(3\)-ádicas a
$$q_n=\frac{q_{n-2}}{q_{n-1}}$$
obtenemos
$$a_n=a_{n-2}-a_{n-1},\qquad b_n=b_{n-2}-b_{n-1},$$
con condiciones iniciales
$$a_1=2,\ a_2=-1,\qquad b_1=0,\ b_2=1.$$
Si ahora definimos
$$A_n=(-1)^{n+1}a_n,\qquad B_n=(-1)^n b_n,$$
entonces ambas sucesiones satisfacen la recurrencia habitual de Fibonacci:
$$A_n=A_{n-1}+A_{n-2},\qquad B_n=B_{n-1}+B_{n-2}.$$
Los valores iniciales las identifican como
$$A_n=L_{n-1},\qquad B_n=F_{n-1},$$
donde
$$F_0=0,\ F_1=1,\qquad L_0=2,\ L_1=1.$$
Por tanto,
$$a_n=(-1)^{n+1}L_{n-1},\qquad b_n=(-1)^nF_{n-1}.$$
El signo obedece una relación análoga. De \(q_n=q_{n-2}/q_{n-1}\) se deduce
$$\varepsilon_n=\varepsilon_{n-2}\varepsilon_{n-1},\qquad \varepsilon_1=+1,\ \varepsilon_2=-1,$$
y en consecuencia
$$\varepsilon_n=(-1)^{F_{n-1}}.$$
Sea \(k=n-1\) y definamos
$$\sigma=(-1)^{F_k}.$$
Entonces la sucesión normalizada tiene la forma exacta
$$q_n=\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n \text{ impar},\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n \text{ par}. \end{cases}$$
Multiplicando por \(25\),
$$u_n=25q_n=25\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n \text{ impar},\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n \text{ par}. \end{cases}$$
Para escribir las coordenadas de forma simétrica, definimos \((\alpha,\beta)\) según la paridad:
$$n \text{ impar}: \alpha=2^{L_k},\ \beta=3^{F_k},\qquad n \text{ par}: \alpha=3^{F_k},\ \beta=2^{L_k}.$$
Así, en ambos casos \(u_n=25\sigma\alpha/\beta\), y al sustituir se obtiene
$$\boxed{x_n=\sigma\frac{3\alpha^2+4\beta^2}{\alpha\beta},\qquad y_n=\sigma\frac{4\alpha^2-3\beta^2}{\alpha\beta}.}$$
Ésta es exactamente la forma algebraica utilizada por el algoritmo modular.
El checksum se forma con las fracciones reducidas, así que hay que conocer el factor común entre cada numerador bruto y el denominador bruto \(\alpha\beta\).
Si \(n\) es impar, \(\alpha\) es una potencia de \(2\) y \(\beta\) una potencia de \(3\). Para \(n\ge 3\), \(\alpha\) es múltiplo de \(8\) y \(\beta\) de \(3\). Entonces
$$3\alpha^2+4\beta^2\ \text{es divisible por}\ 12,$$
pero tras dividir entre \(12\) ya no queda ningún factor adicional \(2\) o \(3\). En cambio,
$$4\alpha^2-3\beta^2\equiv 1 \pmod 3,\qquad 4\alpha^2-3\beta^2\equiv 5 \pmod 8,$$
de modo que es coprimo con \(\alpha\beta\). Por lo tanto
$$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=\begin{cases}4,&n=1,\\12,&n\ge 3\text{ impar},\end{cases}\qquad \gcd(4\alpha^2-3\beta^2,\alpha\beta)=1\ \text{para }n\text{ impar}.$$
Si \(n\) es par, se invierten los papeles de las potencias de \(2\) y \(3\). Entonces \(3\alpha^2+4\beta^2\) ya está reducido, mientras que el otro numerador tiene exactamente un factor \(3\) y, para \(n\ge 4\), exactamente dos factores \(2\):
$$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=1\ \text{para }n\text{ par},$$
$$\gcd(4\alpha^2-3\beta^2,\alpha\beta)=\begin{cases}6,&n=2,\\12,&n\ge 4\text{ par}.\end{cases}$$
Ésos son precisamente los pequeños factores de reducción aplicados antes de construir el checksum.
Este índice aparece como punto de verificación. Aquí \(k=6\), luego
$$F_6=8,\qquad L_6=18,\qquad \sigma=(-1)^8=1.$$
Como \(7\) es impar, tomamos
$$\alpha=2^{18}=262144,\qquad \beta=3^8=6561.$$
Entonces
$$x_7=\frac{3\alpha^2+4\beta^2}{\alpha\beta}=\frac{206330617092}{1719926784}=\frac{17194218091}{143327232},$$
donde la reducción es por \(12\), y
$$y_7=\frac{4\alpha^2-3\beta^2}{\alpha\beta}=\frac{274748766781}{1719926784},$$
que ya está irreducible. Así se recuperan exactamente los valores racionales de control.
Sea \(M=10^9+7\). Como \(M\) es primo y ni \(2\) ni \(3\) son cero módulo \(M\), los exponentes pueden reducirse módulo
$$M-1=10^9+6.$$
Por eso la implementación calcula \(F_k\) y \(F_{k+1}\) módulo \(M-1\), y después reconstruye
$$L_k=2F_{k+1}-F_k.$$
El par de Fibonacci se obtiene con fast doubling:
$$F_{2m}=F_m(2F_{m+1}-F_m),\qquad F_{2m+1}=F_m^2+F_{m+1}^2.$$
Una vez conocidos \(F_k\) y \(L_k\), se evalúan \(2^{L_k}\) y \(3^{F_k}\) módulo \(M\). Las divisiones por \(4\), \(6\) o \(12\) se convierten en multiplicaciones por inversos modulares:
$$a^{-1}\equiv a^{M-2}\pmod M.$$
El signo también se determina sin coste grande: la paridad de Fibonacci tiene período \(3\), así que \(F_k\) es par exactamente cuando \(k\equiv 0\pmod 3\). En ese caso \(\sigma=+1\); en los demás, \(\sigma=-1\).
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero calculan \(k=n-1\). Luego obtienen \(F_k\) y \(F_{k+1}\) módulo \(10^9+6\) mediante fast doubling, deducen \(L_k\), escogen la rama correcta de paridad para \((\alpha,\beta)\), forman los dos numeradores brutos y el denominador bruto común módulo \(10^9+7\), aplican los factores de reducción conocidos usando inversos modulares y finalmente suman las cuatro piezas reducidas. La versión en C++ además contrasta la fórmula con aritmética racional exacta para índices pequeños, confirmando que el atajo modular reproduce exactamente el mismo resultado.
Fast doubling calcula los datos de Fibonacci en \(O(\log n)\) tiempo. Las potencias modulares cuestan \(O(\log M)\), que es constante frente al crecimiento de \(n\). En consecuencia, el solucionador principal funciona en \(O(\log n)\) tiempo y \(O(1)\) memoria. Por eso un índice como \(11^{14}\) es perfectamente manejable.
题目给出双曲线上的有理点序列 \(P_n=(x_n,y_n)\)。如果把
$$x_n=\frac{a_n}{b_n},\qquad y_n=\frac{c_n}{d_n}$$
都写成最简分数且分母为正，那么要求的量就是
$$C_n \equiv a_n+b_n+c_n+d_n \pmod{10^9+7}.$$
困难在于目标下标极大，逐项做有理数递推完全不可行。实现采用的思路是先把点坐标化成闭式，再直接在 \(10^9+7\) 模下计算。
实现先引入辅助序列
$$u_1=100,\qquad u_2=-\frac{75}{2},\qquad u_n=\frac{25u_{n-2}}{u_{n-1}}\qquad (n\ge 3).$$
再用它恢复坐标
$$x_n=\frac{3u_n^2+2500}{25u_n},\qquad y_n=\frac{4u_n^2-1875}{25u_n}.$$
这两个式子马上给出
$$3x_n+4y_n=u_n,\qquad 4x_n-3y_n=\frac{625}{u_n}.$$
两式相乘可得
$$\boxed{(3x_n+4y_n)(4x_n-3y_n)=625,}$$
因此所有点都落在同一条双曲线上，而 \(u_n\) 就是这条曲线的一个有理参数。
令
$$q_n=\frac{u_n}{25}.$$
则递推简化为
$$q_1=4,\qquad q_2=-\frac{3}{2},\qquad q_n=\frac{q_{n-2}}{q_{n-1}}\qquad (n\ge 3).$$
这样一来，序列中只剩下素数 \(2\) 和 \(3\) 的幂，问题就转化为指数和符号的递推。
把每一项写成
$$q_n=\varepsilon_n\,2^{a_n}3^{b_n},\qquad \varepsilon_n\in\{-1,+1\},$$
其中负指数表示相应质因子出现在分母中。对
$$q_n=\frac{q_{n-2}}{q_{n-1}}$$
分别取 \(2\)-进与 \(3\)-进指数，得到
$$a_n=a_{n-2}-a_{n-1},\qquad b_n=b_{n-2}-b_{n-1},$$
初值为
$$a_1=2,\ a_2=-1,\qquad b_1=0,\ b_2=1.$$
现在定义
$$A_n=(-1)^{n+1}a_n,\qquad B_n=(-1)^n b_n.$$
那么它们都满足标准的 Fibonacci 递推
$$A_n=A_{n-1}+A_{n-2},\qquad B_n=B_{n-1}+B_{n-2}.$$
由初值可唯一识别出
$$A_n=L_{n-1},\qquad B_n=F_{n-1},$$
这里
$$F_0=0,\ F_1=1,\qquad L_0=2,\ L_1=1.$$
所以
$$a_n=(-1)^{n+1}L_{n-1},\qquad b_n=(-1)^nF_{n-1}.$$
符号同样满足递推。由 \(q_n=q_{n-2}/q_{n-1}\) 可得
$$\varepsilon_n=\varepsilon_{n-2}\varepsilon_{n-1},\qquad \varepsilon_1=+1,\ \varepsilon_2=-1,$$
从而
$$\varepsilon_n=(-1)^{F_{n-1}}.$$
记 \(k=n-1\)，再设
$$\sigma=(-1)^{F_k}.$$
则归一化后的序列精确地等于
$$q_n=\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n \text{ 为奇数},\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n \text{ 为偶数}. \end{cases}$$
于是
$$u_n=25q_n=25\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n \text{ 为奇数},\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n \text{ 为偶数}. \end{cases}$$
为了把坐标公式写成统一形式，按奇偶定义 \((\alpha,\beta)\)：
$$n \text{ 为奇数}: \alpha=2^{L_k},\ \beta=3^{F_k},\qquad n \text{ 为偶数}: \alpha=3^{F_k},\ \beta=2^{L_k}.$$
于是两种情况下都有 \(u_n=25\sigma\alpha/\beta\)，代入可得
$$\boxed{x_n=\sigma\frac{3\alpha^2+4\beta^2}{\alpha\beta},\qquad y_n=\sigma\frac{4\alpha^2-3\beta^2}{\alpha\beta}.}$$
这正是实现进行模运算时使用的核心公式。
题目要的是最简分数，因此必须知道每个原始分子与原始分母 \(\alpha\beta\) 的公因子。
当 \(n\) 为奇数时，\(\alpha\) 是 \(2\) 的幂，\(\beta\) 是 \(3\) 的幂。若 \(n\ge 3\)，则 \(\alpha\) 至少被 \(8\) 整除，\(\beta\) 至少被 \(3\) 整除。这时
$$3\alpha^2+4\beta^2\ \text{恰好与分母共有因子}\ 12,$$
因为除以 \(12\) 后既不是偶数，也不再被 \(3\) 整除。另一方面，
$$4\alpha^2-3\beta^2\equiv 1 \pmod 3,\qquad 4\alpha^2-3\beta^2\equiv 5 \pmod 8,$$
所以它与 \(\alpha\beta\) 互素。于是
$$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=\begin{cases}4,&n=1,\\12,&n\ge 3\text{ 且为奇数},\end{cases}\qquad \gcd(4\alpha^2-3\beta^2,\alpha\beta)=1\ \text{对奇数 }n\text{ 成立}.$$
当 \(n\) 为偶数时，\(2\) 与 \(3\) 的角色互换。此时 \(3\alpha^2+4\beta^2\) 本身已经最简；而另一个分子恰好带有一个因子 \(3\)，并且当 \(n\ge 4\) 时恰好再带有两个因子 \(2\)：
$$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=1\ \text{对偶数 }n\text{ 成立},$$
$$\gcd(4\alpha^2-3\beta^2,\alpha\beta)=\begin{cases}6,&n=2,\\12,&n\ge 4\text{ 且为偶数}.\end{cases}$$
实现正是利用这些固定的小公因子来做约分，而不是在大整数上再跑一次通用最大公约数。
这个下标是实现中的校验点之一。此时 \(k=6\)，所以
$$F_6=8,\qquad L_6=18,\qquad \sigma=(-1)^8=1.$$
由于 \(7\) 是奇数，取
$$\alpha=2^{18}=262144,\qquad \beta=3^8=6561.$$
于是
$$x_7=\frac{3\alpha^2+4\beta^2}{\alpha\beta}=\frac{206330617092}{1719926784}=\frac{17194218091}{143327232},$$
其中约分因子为 \(12\)；并且
$$y_7=\frac{4\alpha^2-3\beta^2}{\alpha\beta}=\frac{274748766781}{1719926784},$$
本身已经是最简分数。这与实现用于验证的精确有理数结果完全一致。
记 \(M=10^9+7\)。因为 \(M\) 是素数，而且 \(2\)、\(3\) 在模 \(M\) 下都非零，所以指数可以先对
$$M-1=10^9+6$$
取模。实现因此先在 \(M-1\) 模下计算 \(F_k\) 与 \(F_{k+1}\)，再由
$$L_k=2F_{k+1}-F_k$$
恢复 Lucas 指数。Fibonacci 对由 fast doubling 得到：
$$F_{2m}=F_m(2F_{m+1}-F_m),\qquad F_{2m+1}=F_m^2+F_{m+1}^2.$$
得到 \(F_k\) 和 \(L_k\) 后，就可以在模 \(M\) 下计算 \(2^{L_k}\) 与 \(3^{F_k}\)。除以 \(4\)、\(6\)、\(12\) 则用模逆完成：
$$a^{-1}\equiv a^{M-2}\pmod M.$$
符号也很好处理：Fibonacci 奇偶性以 \(3\) 为周期，因此 \(F_k\) 为偶数当且仅当 \(k\equiv 0\pmod 3\)。这时 \(\sigma=+1\)，否则 \(\sigma=-1\)。
C++、Python 和 Java 三个实现的流程完全一致。先计算 \(k=n-1\)，再用 fast doubling 在 \(10^9+6\) 模下得到 \(F_k\) 与 \(F_{k+1}\)，据此求出 \(L_k\)，按奇偶选择正确的 \((\alpha,\beta)\)，然后在 \(10^9+7\) 模下形成两个原始分子和公共原始分母。之后利用已经证明好的固定约分因子，通过模逆完成“除法”，最后把四个约分后的部分相加。C++ 实现还对若干小下标做了精确有理数交叉验证，从而确认这个模算法并不是近似，而是与精确结果完全相同。
fast doubling 求 Fibonacci 只需 \(O(\log n)\) 时间。模幂运算是 \(O(\log M)\)，相对于 \(n\) 的增长可以视为常数规模。因此主算法总时间复杂度为 \(O(\log n)\)，空间复杂度为 \(O(1)\)。这就是为什么 \(11^{14}\) 这样的超大下标仍然可以直接处理。
Последовательность задает рациональные точки \(P_n=(x_n,y_n)\) на одной фиксированной гиперболе. Если
$$x_n=\frac{a_n}{b_n},\qquad y_n=\frac{c_n}{d_n}$$
записаны в несократимом виде с положительными знаменателями, то требуется вычислить
$$C_n \equiv a_n+b_n+c_n+d_n \pmod{10^9+7}.$$
Целевой индекс огромен, поэтому прямой прогон рациональной рекурсии бесполезен. Вместо этого решение выводит замкнутые формулы для координат и вычисляет их сразу по модулю \(10^9+7\).
Решение начинается со вспомогательной последовательности
$$u_1=100,\qquad u_2=-\frac{75}{2},\qquad u_n=\frac{25u_{n-2}}{u_{n-1}}\qquad (n\ge 3).$$
Координаты точки затем выражаются как
$$x_n=\frac{3u_n^2+2500}{25u_n},\qquad y_n=\frac{4u_n^2-1875}{25u_n}.$$
Из этих формул сразу следуют две линейные комбинации:
$$3x_n+4y_n=u_n,\qquad 4x_n-3y_n=\frac{625}{u_n}.$$
Их произведение равно
$$\boxed{(3x_n+4y_n)(4x_n-3y_n)=625,}$$
то есть все точки действительно лежат на одной и той же гиперболе. Следовательно, \(u_n\) является рациональным параметром этой кривой.
Положим
$$q_n=\frac{u_n}{25}.$$
Тогда рекурсия упрощается до
$$q_1=4,\qquad q_2=-\frac{3}{2},\qquad q_n=\frac{q_{n-2}}{q_{n-1}}\qquad (n\ge 3).$$
Это нормализованное представление важно тем, что в нем участвуют только простые \(2\) и \(3\). Значит, структуру последовательности можно полностью описать через показатели степеней и знак.
Запишем каждый член в виде
$$q_n=\varepsilon_n\,2^{a_n}3^{b_n},\qquad \varepsilon_n\in\{-1,+1\},$$
где отрицательные показатели означают, что соответствующий множитель находится в знаменателе. Из равенства
$$q_n=\frac{q_{n-2}}{q_{n-1}}$$
получаем для \(2\)-адической и \(3\)-адической оценок
$$a_n=a_{n-2}-a_{n-1},\qquad b_n=b_{n-2}-b_{n-1},$$
с начальными значениями
$$a_1=2,\ a_2=-1,\qquad b_1=0,\ b_2=1.$$
Теперь введем
$$A_n=(-1)^{n+1}a_n,\qquad B_n=(-1)^n b_n.$$
Обе последовательности удовлетворяют обычной рекурсии Фибоначчи:
$$A_n=A_{n-1}+A_{n-2},\qquad B_n=B_{n-1}+B_{n-2}.$$
По начальным значениям сразу видно, что
$$A_n=L_{n-1},\qquad B_n=F_{n-1},$$
где
$$F_0=0,\ F_1=1,\qquad L_0=2,\ L_1=1.$$
Следовательно,
$$a_n=(-1)^{n+1}L_{n-1},\qquad b_n=(-1)^nF_{n-1}.$$
Знак подчиняется такой же простой схеме. Из \(q_n=q_{n-2}/q_{n-1}\) следует
$$\varepsilon_n=\varepsilon_{n-2}\varepsilon_{n-1},\qquad \varepsilon_1=+1,\ \varepsilon_2=-1,$$
а значит
$$\varepsilon_n=(-1)^{F_{n-1}}.$$
Положим \(k=n-1\) и
$$\sigma=(-1)^{F_k}.$$
Тогда нормализованная последовательность имеет точную форму
$$q_n=\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n \text{ нечетно},\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n \text{ четно}. \end{cases}$$
Следовательно,
$$u_n=25q_n=25\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n \text{ нечетно},\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n \text{ четно}. \end{cases}$$
Чтобы записать координаты симметрично, введем \((\alpha,\beta)\) по четности:
$$n \text{ нечетно}: \alpha=2^{L_k},\ \beta=3^{F_k},\qquad n \text{ четно}: \alpha=3^{F_k},\ \beta=2^{L_k}.$$
Тогда в обеих ветвях \(u_n=25\sigma\alpha/\beta\), и после подстановки получаем
$$\boxed{x_n=\sigma\frac{3\alpha^2+4\beta^2}{\alpha\beta},\qquad y_n=\sigma\frac{4\alpha^2-3\beta^2}{\alpha\beta}.}$$
Именно эта форма и используется в основном вычислении по модулю.
Поскольку в ответ входит сумма числителей и знаменателей уже сокращенных дробей, нужно точно знать общий делитель каждого сырого числителя с сырым знаменателем \(\alpha\beta\).
При нечетном \(n\) число \(\alpha\) является степенью двойки, а \(\beta\) степенью тройки. Для \(n\ge 3\) имеем делимость \(\alpha\) на \(8\) и \(\beta\) на \(3\). Тогда
$$3\alpha^2+4\beta^2\ \text{имеет с }\alpha\beta\ \text{ровно общий множитель}\ 12,$$
потому что после деления на \(12\) результат уже нечетен и не делится на \(3\). А второй числитель удовлетворяет сравнениям
$$4\alpha^2-3\beta^2\equiv 1 \pmod 3,\qquad 4\alpha^2-3\beta^2\equiv 5 \pmod 8,$$
поэтому он взаимно прост с \(\alpha\beta\). Отсюда
$$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=\begin{cases}4,&n=1,\\12,&n\ge 3\text{ нечетно},\end{cases}\qquad \gcd(4\alpha^2-3\beta^2,\alpha\beta)=1\ \text{для нечетного }n.$$
При четном \(n\) роли степеней \(2\) и \(3\) меняются местами. Тогда \(3\alpha^2+4\beta^2\) уже несократимо, а у второго числителя есть ровно один множитель \(3\) и, если \(n\ge 4\), ровно два множителя \(2\):
$$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=1\ \text{для четного }n,$$
$$\gcd(4\alpha^2-3\beta^2,\alpha\beta)=\begin{cases}6,&n=2,\\12,&n\ge 4\text{ четно}.\end{cases}$$
Именно эти фиксированные множители и выносятся в реализации перед формированием контрольной суммы.
Этот индекс используется как контрольный. Здесь \(k=6\), поэтому
$$F_6=8,\qquad L_6=18,\qquad \sigma=(-1)^8=1.$$
Так как \(7\) нечетно, берем
$$\alpha=2^{18}=262144,\qquad \beta=3^8=6561.$$
Тогда
$$x_7=\frac{3\alpha^2+4\beta^2}{\alpha\beta}=\frac{206330617092}{1719926784}=\frac{17194218091}{143327232},$$
причем сокращение происходит на \(12\), а также
$$y_7=\frac{4\alpha^2-3\beta^2}{\alpha\beta}=\frac{274748766781}{1719926784},$$
и эта дробь уже несократима. Именно такие рациональные значения используются для проверки формулы.
Пусть \(M=10^9+7\). Так как \(M\) простое и ни \(2\), ни \(3\) не равны нулю по модулю \(M\), показатели можно сокращать по модулю
$$M-1=10^9+6.$$
Поэтому реализация вычисляет \(F_k\) и \(F_{k+1}\) по модулю \(M-1\), а затем восстанавливает
$$L_k=2F_{k+1}-F_k.$$
Пара чисел Фибоначчи находится методом fast doubling:
$$F_{2m}=F_m(2F_{m+1}-F_m),\qquad F_{2m+1}=F_m^2+F_{m+1}^2.$$
После этого степени \(2^{L_k}\) и \(3^{F_k}\) вычисляются уже по модулю \(M\). Деление на \(4\), \(6\) и \(12\) заменяется умножением на обратные элементы:
$$a^{-1}\equiv a^{M-2}\pmod M.$$
Знак тоже определяется мгновенно: четность чисел Фибоначчи имеет период \(3\), поэтому \(F_k\) четно тогда и только тогда, когда \(k\equiv 0\pmod 3\). В этом случае \(\sigma=+1\), иначе \(\sigma=-1\).
Реализации на C++, Python и Java выполняют один и тот же набор шагов. Сначала вычисляется \(k=n-1\). Затем fast doubling дает \(F_k\) и \(F_{k+1}\) по модулю \(10^9+6\), из них восстанавливается \(L_k\), по четности выбирается нужная ветвь для \((\alpha,\beta)\), строятся два сырых числителя и общий сырой знаменатель по модулю \(10^9+7\), после чего применяются заранее доказанные множители сокращения через модульные обратные. В конце четыре сокращенных остатка суммируются. Реализация на C++ дополнительно сверяет формулу с точной рациональной арифметикой для малых индексов, что подтверждает полное совпадение с точным ответом.
Метод fast doubling вычисляет данные Фибоначчи за \(O(\log n)\) времени. Модульное возведение в степень требует \(O(\log M)\), то есть это постоянная величина по сравнению с ростом \(n\). В итоге основной алгоритм работает за \(O(\log n)\) времени и использует \(O(1)\) памяти. Поэтому индекс порядка \(11^{14}\) обрабатывается без проблем.
تعطي المسألة متتالية من النقاط النسبية \(P_n=(x_n,y_n)\) على قطع زائد ثابت. وإذا كتبنا
$$x_n=\frac{a_n}{b_n},\qquad y_n=\frac{c_n}{d_n}$$
في أبسط صورة وبمقامات موجبة، فإن القيمة المطلوبة هي
$$C_n \equiv a_n+b_n+c_n+d_n \pmod{10^9+7}.$$
ولأن الفهرس المطلوب هائل جدًا، فإن تتبّع العلاقة النسبية خطوة بخطوة غير عملي. لذلك تعتمد الحلول على استخراج صيغة مغلقة للإحداثيين ثم تقييمها مباشرة بترديد \(10^9+7\).
تبدأ التطبيقات بالمتتالية المساعدة
$$u_1=100,\qquad u_2=-\frac{75}{2},\qquad u_n=\frac{25u_{n-2}}{u_{n-1}}\qquad (n\ge 3).$$
ثم تستعيد الإحداثيات من خلال
$$x_n=\frac{3u_n^2+2500}{25u_n},\qquad y_n=\frac{4u_n^2-1875}{25u_n}.$$
ومن هاتين العلاقتين نحصل فورًا على
$$3x_n+4y_n=u_n,\qquad 4x_n-3y_n=\frac{625}{u_n}.$$
وبضربهما يظهر أن
$$\boxed{(3x_n+4y_n)(4x_n-3y_n)=625,}$$
أي إن جميع النقاط تقع على القطع الزائد نفسه، وأن \(u_n\) يعمل وسيطًا نسبيًا لهذا المنحنى.
لنعرّف
$$q_n=\frac{u_n}{25}.$$
عندها تصبح العلاقة التكرارية أبسط بكثير:
$$q_1=4,\qquad q_2=-\frac{3}{2},\qquad q_n=\frac{q_{n-2}}{q_{n-1}}\qquad (n\ge 3).$$
وهنا تظهر الفكرة الأساسية: كل الحدود تتكون فقط من قوى \(2\) و\(3\)، ولذلك يمكن فهم البنية كاملة عبر الأسس والإشارة.
نكتب كل حد على الصورة
$$q_n=\varepsilon_n\,2^{a_n}3^{b_n},\qquad \varepsilon_n\in\{-1,+1\},$$
حيث تعني الأسس السالبة وجود العامل في المقام. وبأخذ التقييمين \(2\)-الأدي و\(3\)-الأدي في العلاقة
$$q_n=\frac{q_{n-2}}{q_{n-1}}$$
نحصل على
$$a_n=a_{n-2}-a_{n-1},\qquad b_n=b_{n-2}-b_{n-1},$$
مع القيم الابتدائية
$$a_1=2,\ a_2=-1,\qquad b_1=0,\ b_2=1.$$
الآن نعرّف
$$A_n=(-1)^{n+1}a_n,\qquad B_n=(-1)^n b_n.$$
فتخضع المتتاليتان للعلاقة القياسية لفيبوناتشي:
$$A_n=A_{n-1}+A_{n-2},\qquad B_n=B_{n-1}+B_{n-2}.$$
ومن القيم الابتدائية يتبين مباشرة أن
$$A_n=L_{n-1},\qquad B_n=F_{n-1},$$
حيث
$$F_0=0,\ F_1=1,\qquad L_0=2,\ L_1=1.$$
ومن ثم
$$a_n=(-1)^{n+1}L_{n-1},\qquad b_n=(-1)^nF_{n-1}.$$
أما الإشارة نفسها فتتبع علاقة مماثلة. فمن
$$q_n=\frac{q_{n-2}}{q_{n-1}}$$
نستنتج
$$\varepsilon_n=\varepsilon_{n-2}\varepsilon_{n-1},\qquad \varepsilon_1=+1,\ \varepsilon_2=-1,$$
وبالتالي
$$\varepsilon_n=(-1)^{F_{n-1}}.$$
لنضع \(k=n-1\) و
$$\sigma=(-1)^{F_k}.$$
عندها تأخذ المتتالية المطَبَّعة الصيغة الدقيقة
$$q_n=\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n\equiv 1 \pmod 2,\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n\equiv 0 \pmod 2. \end{cases}$$
ومن ثم
$$u_n=25q_n=25\sigma\begin{cases} \dfrac{2^{L_k}}{3^{F_k}}, & n\equiv 1 \pmod 2,\\[6pt] \dfrac{3^{F_k}}{2^{L_k}}, & n\equiv 0 \pmod 2. \end{cases}$$
ولكي تصبح الصيغة متناظرة، نأخذ \(\alpha=2^{L_k}\) و\(\beta=3^{F_k}\) عندما \(n\equiv 1 \pmod 2\)، ونأخذ \(\alpha=3^{F_k}\) و\(\beta=2^{L_k}\) عندما \(n\equiv 0 \pmod 2\).
وعندئذ يكون \(u_n=25\sigma\alpha/\beta\) في الحالتين، ويعطي التعويض
$$\boxed{x_n=\sigma\frac{3\alpha^2+4\beta^2}{\alpha\beta},\qquad y_n=\sigma\frac{4\alpha^2-3\beta^2}{\alpha\beta}.}$$
وهذه هي الصيغة الجبرية التي يعتمد عليها التنفيذ المعياري.
بما أن قيمة التحقق تعتمد على الكسور بعد الاختزال، فلا بد من معرفة القاسم المشترك بين كل بسط خام وبين المقام الخام \(\alpha\beta\).
عندما يكون \(n\) فرديًا، تكون \(\alpha\) قوة للعدد \(2\) و\(\beta\) قوة للعدد \(3\). وإذا كان \(n\ge 3\) فإن \(\alpha\) يقبل القسمة على \(8\) و\(\beta\) يقبل القسمة على \(3\). عندئذٍ
وفي هذه الحالة يكون \(3\alpha^2+4\beta^2\) قابلاً للقسمة على \(12\) بالضبط.
لأن الناتج بعد القسمة على \(12\) لا يبقى زوجيًا ولا يبقى من مضاعفات \(3\). أما البسط الآخر فيحقق
$$4\alpha^2-3\beta^2\equiv 1 \pmod 3,\qquad 4\alpha^2-3\beta^2\equiv 5 \pmod 8,$$
وبالتالي فهو أولي نسبيًا مع \(\alpha\beta\). لذلك
$$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=\begin{cases}4,&n=1,\\12,&n\ge 3,\ n\equiv 1 \pmod 2,\end{cases}\qquad \gcd(4\alpha^2-3\beta^2,\alpha\beta)=1\ \text{for }n\equiv 1 \pmod 2.$$
وعندما يكون \(n\) زوجيًا، تنعكس أدوار قوى \(2\) و\(3\). فيصبح \(3\alpha^2+4\beta^2\) مختزلًا أصلًا، بينما يمتلك البسط الآخر عاملًا واحدًا من \(3\)، ولـ \(n\ge 4\) عاملين بالضبط من \(2\):
$$\gcd(3\alpha^2+4\beta^2,\alpha\beta)=1\ \text{for }n\equiv 0 \pmod 2,$$
$$\gcd(4\alpha^2-3\beta^2,\alpha\beta)=\begin{cases}6,&n=2,\\12,&n\ge 4,\ n\equiv 0 \pmod 2.\end{cases}$$
وهذه هي بالضبط العوامل الصغيرة الثابتة التي يطبقها التنفيذ قبل تكوين قيمة التحقق.
هذا الفهرس من نقاط التحقق في التنفيذ. هنا \(k=6\)، ولذلك
$$F_6=8,\qquad L_6=18,\qquad \sigma=(-1)^8=1.$$
ولأن \(7\) فردي فنأخذ
$$\alpha=2^{18}=262144,\qquad \beta=3^8=6561.$$
ومن ثم
$$x_7=\frac{3\alpha^2+4\beta^2}{\alpha\beta}=\frac{206330617092}{1719926784}=\frac{17194218091}{143327232},$$
وفيه عامل اختزال مقداره \(12\)، وكذلك
$$y_7=\frac{4\alpha^2-3\beta^2}{\alpha\beta}=\frac{274748766781}{1719926784},$$
وهذه الكسرة مختزلة أصلًا. وهكذا نحصل على نفس القيم النسبية الدقيقة المستخدمة في التحقق.
لنرمز إلى \(M=10^9+7\). بما أن \(M\) أولي و\(2\) و\(3\) غير منعدمين بترديد \(M\)، يمكن اختزال الأسس بترديد
$$M-1=10^9+6.$$
ولهذا تحسب التطبيقات \(F_k\) و\(F_{k+1}\) بترديد \(M-1\)، ثم تستنتج
$$L_k=2F_{k+1}-F_k.$$
ويُحسب زوج فيبوناتشي بخوارزمية المضاعفة السريعة:
$$F_{2m}=F_m(2F_{m+1}-F_m),\qquad F_{2m+1}=F_m^2+F_{m+1}^2.$$
وبعد معرفة \(F_k\) و\(L_k\)، نحسب \(2^{L_k}\) و\(3^{F_k}\) بترديد \(M\). أما القسمة على \(4\) أو \(6\) أو \(12\) فتتحول إلى ضرب في المعكوس المعياري:
$$a^{-1}\equiv a^{M-2}\pmod M.$$
والإشارة نفسها يسهل تحديدها، لأن زوجية أعداد فيبوناتشي دورها \(3\). ومن ثم يكون \(F_k\) زوجيًا إذا وفقط إذا كان \(k\equiv 0\pmod 3\)، وعندها \(\sigma=+1\)، وإلا فالقيمة \(\sigma=-1\).
تتبع تطبيقات C++ وPython وJava المسار نفسه. فهي تحسب أولًا \(k=n-1\)، ثم تستخرج \(F_k\) و\(F_{k+1}\) بترديد \(10^9+6\) بخوارزمية المضاعفة السريعة، وتستعيد \(L_k\)، وتختار الفرع الصحيح لـ \((\alpha,\beta)\) بحسب الزوجية، وتكوّن البسطين الخامين والمقام الخام المشترك بترديد \(10^9+7\). بعد ذلك تطبق عوامل الاختزال المعروفة باستخدام المعكوسات المعيارية، وفي النهاية تجمع الأجزاء الأربعة بعد الاختزال. كما أن تنفيذ C++ يجري تحققًا إضافيًا على فهارس صغيرة باستخدام حساب نسبي دقيق، ليتأكد أن الاختصار المعياري يعطي النتيجة نفسها تمامًا.
تحسب خوارزمية المضاعفة السريعة بيانات فيبوناتشي في زمن \(O(\log n)\). أما الأسس المعيارية فتحتاج إلى \(O(\log M)\)، وهو حد ثابت عمليًا مقارنةً بنمو \(n\). لذلك تعمل الخوارزمية الرئيسية في \(O(\log n)\) زمنًا و\(O(1)\) ذاكرة. ولهذا يمكن التعامل مع فهرس مثل \(11^{14}\) بسهولة.