For each \(n\in\{1,\dots,30\}\), let \(a_n\) be the largest real root of
$$x^3-2^n x^2+n=0.$$
The task is to compute
$$\sum_{n=1}^{30}\left\lfloor a_n^{987654321}\right\rfloor \pmod{10^8}.$$
A direct floating-point evaluation of such enormous powers would be fragile and unnecessary. The local C++, Python, and Java solutions instead turn the problem into an exact linear recurrence modulo \(10^8\).
Write \(c=2^n\) and \(f(x)=x^3-cx^2+n\). The implementations rely on the fact that the cubic has three real roots, with one large positive root and two small roots near the origin.
Indeed,
$$f(-1)=n-1-c<0,\qquad f(0)=n>0,$$
so there is a root \(\gamma\in(-1,0)\). Also,
$$f(1)=n+1-c\le 0,\qquad f(0)=n>0,$$
so there is a root \(\beta\in(0,1]\), with \(\beta=1\) only when \(n=1\). Finally,
$$f(c)=n>0,\qquad f(c-1)=n-(c-1)^2\le 0,$$
so the largest root \(\alpha=a_n\) lies in \((c-1,c)\). Thus the three roots satisfy
$$\gamma\in(-1,0),\qquad \beta\in(0,1],\qquad \alpha\in(2^n-1,2^n).$$
By Vieta's formulas,
$$\alpha+\beta+\gamma=c,\qquad \alpha\beta+\alpha\gamma+\beta\gamma=0,\qquad \alpha\beta\gamma=-n.$$
Let
$$S_k=\alpha^k+\beta^k+\gamma^k.$$
Because every root \(r\in\{\alpha,\beta,\gamma\}\) satisfies
$$r^3=cr^2-n,$$
multiplying by \(r^{k-3}\) gives
$$r^k=cr^{k-1}-nr^{k-3}\qquad (k\ge 3).$$
Summing over the three roots yields the recurrence used in every implementation:
$$\boxed{S_k=cS_{k-1}-nS_{k-3}\qquad (k\ge 3).}$$
The initial values are immediate:
$$S_0=3,$$
$$S_1=\alpha+\beta+\gamma=c,$$
$$S_2=(\alpha+\beta+\gamma)^2-2(\alpha\beta+\alpha\gamma+\beta\gamma)=c^2.$$
So the entire problem is reduced to a third-order linear recurrence.
Let \(m\) be odd and define the small-root contribution
$$\rho_m=\beta^m+\gamma^m.$$
Since \(\gamma<0\) and \(m\) is odd, we have \(\gamma^m<0\). We also know
$$\beta+\gamma=c-\alpha,$$
and because \(\alpha\in(c-1,c)\), this implies
$$0<\beta+\gamma<1.$$
In particular, \(\beta>|\gamma|\). For odd \(m\), monotonicity of \(x\mapsto x^m\) on positive numbers gives
$$\beta^m>|\gamma|^m,$$
hence
$$0<\rho_m=\beta^m-|\gamma|^m.$$
At the same time, \(\beta\le 1\) and \(|\gamma|<1\), so
$$\rho_m<1.$$
Therefore
$$0<\rho_m<1,$$
and since \(\alpha^m=S_m-\rho_m\), we obtain the crucial identity
$$\boxed{\left\lfloor \alpha^m\right\rfloor=\left\lfloor S_m-\rho_m\right\rfloor=S_m-1.}$$
This is exactly why the production code never needs to approximate \(a_n^{987654321}\) directly.
The recurrence has fixed order 3, so the state vector
$$\begin{bmatrix}S_k\\S_{k-1}\\S_{k-2}\end{bmatrix}$$
evolves by
$$\begin{bmatrix}S_k\\S_{k-1}\\S_{k-2}\end{bmatrix} = \begin{bmatrix} c & 0 & -n\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix}S_{k-1}\\S_{k-2}\\S_{k-3}\end{bmatrix}.$$
Hence, for \(m\ge 2\),
$$\begin{bmatrix}S_m\\S_{m-1}\\S_{m-2}\end{bmatrix} = M^{m-2} \begin{bmatrix}S_2\\S_1\\S_0\end{bmatrix}.$$
The solutions compute this power by binary exponentiation, reducing every multiplication modulo \(10^8\). In modular arithmetic the entry \(-n\) is stored as
$$10^8-(n\bmod 10^8),$$
which is why the source code writes the transition matrix with a non-negative last coefficient.
Take \(n=2\), so \(c=4\). Then
$$S_0=3,\qquad S_1=4,\qquad S_2=16.$$
For the odd exponent \(m=3\), the recurrence gives
$$S_3=4\cdot 16-2\cdot 3=58.$$
Since \(0<\beta^3+\gamma^3<1\), we conclude
$$\left\lfloor a_2^3\right\rfloor=S_3-1=57.$$
The C++ implementation performs this kind of spot check numerically for small odd exponents before relying on the modular fast path for the full input.
The three language versions all implement the same pipeline. First, powMod computes \(c=2^n\bmod 10^8\). Then multiplyMatrix and powerMatrix raise the \(3\times 3\) transition matrix to the power \(m-2\). The function computeNewtonSumMod returns \(S_m\bmod 10^8\), handling the base cases \(m=0,1,2\) directly and using matrix exponentiation otherwise.
After that, computeTermMod applies the identity \(\lfloor a_n^m\rfloor\equiv S_m-1\pmod{10^8}\), and solve sums the terms for \(n=1\) through \(30\). The longer C++ file also contains validation helpers: it checks the statement sample \(\lfloor a_2^2\rfloor=14\), verifies the matrix recurrence against a direct iterative recurrence, compares the floor identity against floating-point root calculations on small cases, and tests thread consistency. Those checks justify the method, but the final answer path itself is entirely integer-based.
For one fixed \(n\), the dominant cost is exponentiating a \(3\times 3\) matrix to power \(m-2\), which takes \(O(\log m)\) matrix multiplications. The problem has only 30 values of \(n\), so the total running time is
$$O(30\log m)=O(\log m),$$
with \(O(1)\) auxiliary memory. The C++ version can parallelize the 30 independent \(n\)-values, but that changes only wall-clock time, not asymptotic complexity.
Für jedes \(n\in\{1,\dots,30\}\) sei \(a_n\) die größte reelle Nullstelle von
$$x^3-2^n x^2+n=0.$$
Gesucht ist
$$\sum_{n=1}^{30}\left\lfloor a_n^{987654321}\right\rfloor \pmod{10^8}.$$
Eine direkte Auswertung der riesigen Potenzen mit Gleitkomma wäre unnötig unsauber. Die lokalen Lösungen in C++, Python und Java führen das Problem stattdessen auf eine exakte lineare Rekurrenz modulo \(10^8\) zurück.
Setze \(c=2^n\) und \(f(x)=x^3-cx^2+n\). Die Implementierungen nutzen aus, dass das Polynom drei reelle Nullstellen besitzt: eine große positive und zwei kleine nahe dem Ursprung.
Es gilt
$$f(-1)=n-1-c<0,\qquad f(0)=n>0,$$
also existiert eine Nullstelle \(\gamma\in(-1,0)\). Außerdem
$$f(1)=n+1-c\le 0,\qquad f(0)=n>0,$$
daher gibt es eine Nullstelle \(\beta\in(0,1]\), wobei \(\beta=1\) nur für \(n=1\) auftritt. Schließlich
$$f(c)=n>0,\qquad f(c-1)=n-(c-1)^2\le 0,$$
also liegt die größte Nullstelle \(\alpha=a_n\) im Intervall \((c-1,c)\). Damit gilt
$$\gamma\in(-1,0),\qquad \beta\in(0,1],\qquad \alpha\in(2^n-1,2^n).$$
Mit den Formeln von Viète folgt
$$\alpha+\beta+\gamma=c,\qquad \alpha\beta+\alpha\gamma+\beta\gamma=0,\qquad \alpha\beta\gamma=-n.$$
Definiere
$$S_k=\alpha^k+\beta^k+\gamma^k.$$
Da jede Nullstelle \(r\in\{\alpha,\beta,\gamma\}\) die Gleichung
$$r^3=cr^2-n$$
erfüllt, erhält man nach Multiplikation mit \(r^{k-3}\)
$$r^k=cr^{k-1}-nr^{k-3}\qquad (k\ge 3).$$
Durch Summation über alle drei Nullstellen entsteht genau die Rekurrenz aus dem Quellcode:
$$\boxed{S_k=cS_{k-1}-nS_{k-3}\qquad (k\ge 3).}$$
Die Anfangswerte sind
$$S_0=3,$$
$$S_1=\alpha+\beta+\gamma=c,$$
$$S_2=(\alpha+\beta+\gamma)^2-2(\alpha\beta+\alpha\gamma+\beta\gamma)=c^2.$$
Damit ist das Problem auf eine lineare Rekurrenz dritter Ordnung reduziert.
Für ungerades \(m\) definieren wir den Beitrag der kleinen Nullstellen als
$$\rho_m=\beta^m+\gamma^m.$$
Wegen \(\gamma<0\) und ungeradem \(m\) ist \(\gamma^m<0\). Außerdem gilt
$$\beta+\gamma=c-\alpha,$$
und aus \(\alpha\in(c-1,c)\) folgt
$$0<\beta+\gamma<1.$$
Insbesondere ist \(\beta>|\gamma|\). Für ungerades \(m\) folgt daraus
$$\beta^m>|\gamma|^m,$$
also
$$0<\rho_m=\beta^m-|\gamma|^m.$$
Zugleich gilt \(\beta\le 1\) und \(|\gamma|<1\), also
$$\rho_m<1.$$
Somit
$$0<\rho_m<1,$$
und da \(\alpha^m=S_m-\rho_m\), erhalten wir die Schlüsselformel
$$\boxed{\left\lfloor \alpha^m\right\rfloor=\left\lfloor S_m-\rho_m\right\rfloor=S_m-1.}$$
Genau deshalb berechnet der eigentliche Lösungsweg nie direkt \(a_n^{987654321}\).
Die Rekurrenz hat feste Ordnung 3. Deshalb entwickelt sich der Zustandsvektor
$$\begin{bmatrix}S_k\\S_{k-1}\\S_{k-2}\end{bmatrix}$$
nach der Vorschrift
$$\begin{bmatrix}S_k\\S_{k-1}\\S_{k-2}\end{bmatrix} = \begin{bmatrix} c & 0 & -n\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix}S_{k-1}\\S_{k-2}\\S_{k-3}\end{bmatrix}.$$
Für \(m\ge 2\) also
$$\begin{bmatrix}S_m\\S_{m-1}\\S_{m-2}\end{bmatrix} = M^{m-2} \begin{bmatrix}S_2\\S_1\\S_0\end{bmatrix}.$$
Der Code berechnet diese Potenz mit binärer Exponentiation. Da nur das Resultat modulo \(10^8\) benötigt wird, werden alle Operationen sofort reduziert. Der Eintrag \(-n\) wird im Code deshalb als nichtnegative Zahl
$$10^8-(n\bmod 10^8)$$
gespeichert.
Für \(n=2\) ist \(c=4\). Dann gilt
$$S_0=3,\qquad S_1=4,\qquad S_2=16.$$
Für den ungeraden Exponenten \(m=3\) liefert die Rekurrenz
$$S_3=4\cdot 16-2\cdot 3=58.$$
Da \(0<\beta^3+\gamma^3<1\), folgt
$$\left\lfloor a_2^3\right\rfloor=S_3-1=57.$$
Die C++-Version führt genau solche Stichproben für kleine ungerade Exponenten numerisch aus, bevor sie für den eigentlichen Lauf nur noch die modulare Schnellmethode verwendet.
Alle drei Sprachversionen benutzen dieselbe Struktur. Zuerst berechnet powMod den Wert \(c=2^n\bmod 10^8\). Danach heben multiplyMatrix und powerMatrix die \(3\times 3\)-Übergangsmatrix auf die Potenz \(m-2\). Die Funktion computeNewtonSumMod gibt \(S_m\bmod 10^8\) zurück; die Fälle \(m=0,1,2\) werden direkt behandelt, alle größeren Exponenten per Matrixpotenz.
Anschließend nutzt computeTermMod die Identität \(\lfloor a_n^m\rfloor\equiv S_m-1\pmod{10^8}\), und solve summiert über \(n=1,\dots,30\). Die ausführlichere C++-Datei enthält zusätzlich Validierungen: das Beispiel \(\lfloor a_2^2\rfloor=14\), einen Vergleich zwischen Matrix- und iterativer Rekurrenz, numerische Prüfungen der Bodenfunktion für kleine Fälle und einen Thread-Konsistenztest. Der eigentliche Rechenweg bleibt aber vollständig ganzzahlig.
Für ein festes \(n\) dominiert die Potenzierung einer \(3\times 3\)-Matrix auf die Höhe \(m-2\). Das kostet \(O(\log m)\) Matrixmultiplikationen. Da nur 30 Werte von \(n\) vorkommen, beträgt die Gesamtlaufzeit
$$O(30\log m)=O(\log m),$$
bei \(O(1)\) Zusatzspeicher. Die C++-Implementierung kann die 30 unabhängigen \(n\)-Werte parallel auswerten; an der asymptotischen Ordnung ändert das nichts.
Her \(n\in\{1,\dots,30\}\) için \(a_n\),
$$x^3-2^n x^2+n=0$$
denkleminin en büyük gerçek kökü olsun. İstenen değer
$$\sum_{n=1}^{30}\left\lfloor a_n^{987654321}\right\rfloor \pmod{10^8}$$
ifadesidir. Bu kadar büyük üsler için doğrudan kayan noktalı hesap yapmak hem gereksiz hem de risklidir. Yerel C++, Python ve Java çözümleri bunun yerine problemi \(10^8\) modunda çalışan kesin bir lineer reküransa indirger.
\(c=2^n\) ve \(f(x)=x^3-cx^2+n\) olsun. Uygulama, bu kübiğin üç gerçek kökü olmasını kullanır: biri büyük pozitif, ikisi ise orijine yakın küçük köklerdir.
Gerçekten,
$$f(-1)=n-1-c<0,\qquad f(0)=n>0,$$
olduğu için \(\gamma\in(-1,0)\) aralığında bir kök vardır. Ayrıca
$$f(1)=n+1-c\le 0,\qquad f(0)=n>0,$$
olduğundan \(\beta\in(0,1]\) aralığında bir kök bulunur; \(\beta=1\) yalnızca \(n=1\) için oluşur. Son olarak
$$f(c)=n>0,\qquad f(c-1)=n-(c-1)^2\le 0,$$
olduğu için en büyük kök \(\alpha=a_n\), \((c-1,c)\) aralığındadır. Dolayısıyla
$$\gamma\in(-1,0),\qquad \beta\in(0,1],\qquad \alpha\in(2^n-1,2^n).$$
Vieta bağıntıları da şunları verir:
$$\alpha+\beta+\gamma=c,\qquad \alpha\beta+\alpha\gamma+\beta\gamma=0,\qquad \alpha\beta\gamma=-n.$$
Şimdi
$$S_k=\alpha^k+\beta^k+\gamma^k$$
tanımını yapalım. Her kök \(r\in\{\alpha,\beta,\gamma\}\) için
$$r^3=cr^2-n$$
geçerlidir. Bunu \(r^{k-3}\) ile çarparsak
$$r^k=cr^{k-1}-nr^{k-3}\qquad (k\ge 3)$$
elde ederiz. Üç kök üzerinde toplandığında, çözümlerde kullanılan rekürans ortaya çıkar:
$$\boxed{S_k=cS_{k-1}-nS_{k-3}\qquad (k\ge 3).}$$
Başlangıç değerleri ise
$$S_0=3,$$
$$S_1=\alpha+\beta+\gamma=c,$$
$$S_2=(\alpha+\beta+\gamma)^2-2(\alpha\beta+\alpha\gamma+\beta\gamma)=c^2.$$
Böylece problem üçüncü dereceden lineer bir reküransa dönüşür.
\(m\) tek olsun ve küçük köklerin katkısını
$$\rho_m=\beta^m+\gamma^m$$
olarak tanımlayalım. \(\gamma<0\) ve \(m\) tek olduğundan \(\gamma^m<0\). Ayrıca
$$\beta+\gamma=c-\alpha$$
olup \(\alpha\in(c-1,c)\) nedeniyle
$$0<\beta+\gamma<1.$$
Buradan \(\beta>|\gamma|\) çıkar. Tek kuvvette bu sıralama korunur:
$$\beta^m>|\gamma|^m,$$
dolayısıyla
$$0<\rho_m=\beta^m-|\gamma|^m.$$
Öte yandan \(\beta\le 1\) ve \(|\gamma|<1\) olduğundan
$$\rho_m<1.$$
Sonuç olarak
$$0<\rho_m<1,$$
ve \(\alpha^m=S_m-\rho_m\) eşitliğinden şu temel kimlik elde edilir:
$$\boxed{\left\lfloor \alpha^m\right\rfloor=\left\lfloor S_m-\rho_m\right\rfloor=S_m-1.}$$
Bu yüzden üretim yolunda \(a_n^{987654321}\) doğrudan hesaplanmaz.
Reküransın derecesi sabit olarak 3'tür. Bu nedenle durum vektörü
$$\begin{bmatrix}S_k\\S_{k-1}\\S_{k-2}\end{bmatrix}$$
şu geçişle ilerler:
$$\begin{bmatrix}S_k\\S_{k-1}\\S_{k-2}\end{bmatrix} = \begin{bmatrix} c & 0 & -n\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix}S_{k-1}\\S_{k-2}\\S_{k-3}\end{bmatrix}.$$
Dolayısıyla \(m\ge 2\) için
$$\begin{bmatrix}S_m\\S_{m-1}\\S_{m-2}\end{bmatrix} = M^{m-2} \begin{bmatrix}S_2\\S_1\\S_0\end{bmatrix}.$$
Kod bu kuvveti ikili üs alma ile hesaplar ve her çarpımı hemen \(10^8\) moduna indirger. Modüler aritmetikte \(-n\) katsayısı, kaynak kodda
$$10^8-(n\bmod 10^8)$$
olarak saklanır; bu yüzden geçiş matrisinde negatif sayı görülmez.
\(n=2\) için \(c=4\) olur. O halde
$$S_0=3,\qquad S_1=4,\qquad S_2=16.$$
Tek üs \(m=3\) için rekürans
$$S_3=4\cdot 16-2\cdot 3=58$$
sonucunu verir. \(0<\beta^3+\gamma^3<1\) olduğundan
$$\left\lfloor a_2^3\right\rfloor=S_3-1=57.$$
C++ çözümü, tam hızlı yola güvenmeden önce küçük tek üsler için buna benzer sayısal doğrulamalar yapar.
Üç dildeki çözüm de aynı akışı izler. Önce powMod, \(c=2^n\bmod 10^8\) değerini hesaplar. Sonra multiplyMatrix ve powerMatrix, \(3\times 3\) geçiş matrisini \(m-2\) kuvvetine yükseltir. computeNewtonSumMod fonksiyonu \(S_m\bmod 10^8\) döndürür; \(m=0,1,2\) durumları doğrudan ele alınır, daha büyük üslerde matris üsleme kullanılır.
Ardından computeTermMod, \(\lfloor a_n^m\rfloor\equiv S_m-1\pmod{10^8}\) kimliğini uygular ve solve fonksiyonu \(n=1\) ile \(30\) arasındaki tüm terimleri toplar. Daha uzun olan C++ dosyası ayrıca birkaç doğrulama içerir: \(\lfloor a_2^2\rfloor=14\) örneği, matrisli ve iteratif reküransın karşılaştırılması, küçük örneklerde sayısal kök denetimi ve çok iş parçacıklı tutarlılık testi. Ancak nihai hesap yolu tamamen tamsayı aritmetiğine dayanır.
Sabit bir \(n\) için baskın işlem, \(3\times 3\) matrisin \(m-2\) kuvvetine çıkarılmasıdır; bu da \(O(\log m)\) adet matris çarpımı gerektirir. Problemde yalnızca 30 farklı \(n\) bulunduğu için toplam süre
$$O(30\log m)=O(\log m)$$
olur ve ek bellek \(O(1)\) düzeyindedir. C++ sürümü bağımsız \(n\) değerlerini paralel çalıştırabilir; bu yalnızca pratik süreyi düşürür, matematiksel karmaşıklığı değiştirmez.
Para cada \(n\in\{1,\dots,30\}\), sea \(a_n\) la mayor raíz real de
$$x^3-2^n x^2+n=0.$$
Hay que calcular
$$\sum_{n=1}^{30}\left\lfloor a_n^{987654321}\right\rfloor \pmod{10^8}.$$
Evaluar esas potencias gigantes con aritmética de punto flotante sería frágil e innecesario. Las soluciones locales en C++, Python y Java transforman el problema en una recurrencia lineal exacta módulo \(10^8\).
Escribamos \(c=2^n\) y \(f(x)=x^3-cx^2+n\). La idea central es que el cúbico tiene tres raíces reales: una grande y positiva, y dos pequeñas cerca del origen.
Se tiene
$$f(-1)=n-1-c<0,\qquad f(0)=n>0,$$
así que existe una raíz \(\gamma\in(-1,0)\). Además,
$$f(1)=n+1-c\le 0,\qquad f(0)=n>0,$$
por lo que existe una raíz \(\beta\in(0,1]\), con \(\beta=1\) solo cuando \(n=1\). Finalmente,
$$f(c)=n>0,\qquad f(c-1)=n-(c-1)^2\le 0,$$
de modo que la raíz mayor \(\alpha=a_n\) pertenece a \((c-1,c)\). En resumen,
$$\gamma\in(-1,0),\qquad \beta\in(0,1],\qquad \alpha\in(2^n-1,2^n).$$
Las fórmulas de Viète dan
$$\alpha+\beta+\gamma=c,\qquad \alpha\beta+\alpha\gamma+\beta\gamma=0,\qquad \alpha\beta\gamma=-n.$$
Definimos
$$S_k=\alpha^k+\beta^k+\gamma^k.$$
Cada raíz \(r\in\{\alpha,\beta,\gamma\}\) satisface
$$r^3=cr^2-n,$$
y al multiplicar por \(r^{k-3}\) obtenemos
$$r^k=cr^{k-1}-nr^{k-3}\qquad (k\ge 3).$$
Sumando sobre las tres raíces aparece exactamente la recurrencia usada en el código:
$$\boxed{S_k=cS_{k-1}-nS_{k-3}\qquad (k\ge 3).}$$
Los valores iniciales son
$$S_0=3,$$
$$S_1=\alpha+\beta+\gamma=c,$$
$$S_2=(\alpha+\beta+\gamma)^2-2(\alpha\beta+\alpha\gamma+\beta\gamma)=c^2.$$
Así, el problema queda reducido a una recurrencia lineal de orden 3.
Para \(m\) impar, definimos la contribución de las raíces pequeñas
$$\rho_m=\beta^m+\gamma^m.$$
Como \(\gamma<0\) y \(m\) es impar, \(\gamma^m<0\). Además,
$$\beta+\gamma=c-\alpha,$$
y puesto que \(\alpha\in(c-1,c)\), se sigue que
$$0<\beta+\gamma<1.$$
En particular, \(\beta>|\gamma|\). Para exponentes impares eso implica
$$\beta^m>|\gamma|^m,$$
de modo que
$$0<\rho_m=\beta^m-|\gamma|^m.$$
Por otra parte, \(\beta\le 1\) y \(|\gamma|<1\), así que
$$\rho_m<1.$$
En consecuencia,
$$0<\rho_m<1,$$
y como \(\alpha^m=S_m-\rho_m\), obtenemos la identidad clave
$$\boxed{\left\lfloor \alpha^m\right\rfloor=\left\lfloor S_m-\rho_m\right\rfloor=S_m-1.}$$
Esa es la razón por la que el camino rápido nunca calcula directamente \(a_n^{987654321}\).
La recurrencia tiene orden fijo 3, por lo que el vector de estado
$$\begin{bmatrix}S_k\\S_{k-1}\\S_{k-2}\end{bmatrix}$$
evoluciona según
$$\begin{bmatrix}S_k\\S_{k-1}\\S_{k-2}\end{bmatrix} = \begin{bmatrix} c & 0 & -n\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix}S_{k-1}\\S_{k-2}\\S_{k-3}\end{bmatrix}.$$
Por tanto, para \(m\ge 2\),
$$\begin{bmatrix}S_m\\S_{m-1}\\S_{m-2}\end{bmatrix} = M^{m-2} \begin{bmatrix}S_2\\S_1\\S_0\end{bmatrix}.$$
El programa calcula esa potencia con exponenciación binaria y reduce todo módulo \(10^8\). En aritmética modular, el coeficiente \(-n\) se almacena como
$$10^8-(n\bmod 10^8),$$
que es exactamente lo que aparece en las implementaciones.
Tomemos \(n=2\), de modo que \(c=4\). Entonces
$$S_0=3,\qquad S_1=4,\qquad S_2=16.$$
Para el exponente impar \(m=3\), la recurrencia produce
$$S_3=4\cdot 16-2\cdot 3=58.$$
Como \(0<\beta^3+\gamma^3<1\), concluimos que
$$\left\lfloor a_2^3\right\rfloor=S_3-1=57.$$
La versión en C++ hace este tipo de comprobaciones numéricas en casos pequeños antes de ejecutar el cálculo modular completo.
Las tres versiones usan la misma estructura. Primero, powMod calcula \(c=2^n\bmod 10^8\). Luego, multiplyMatrix y powerMatrix elevan la matriz de transición \(3\times 3\) a la potencia \(m-2\). La función computeNewtonSumMod devuelve \(S_m\bmod 10^8\), tratando de forma directa los casos \(m=0,1,2\) y usando potenciación matricial para el resto.
Después, computeTermMod aplica la identidad \(\lfloor a_n^m\rfloor\equiv S_m-1\pmod{10^8}\), y solve suma los 30 términos. El archivo C++ añade validaciones auxiliares: comprueba el ejemplo \(\lfloor a_2^2\rfloor=14\), verifica la recurrencia matricial contra una versión iterativa, contrasta la identidad del piso con cálculos numéricos de raíces en casos pequeños y revisa la consistencia entre un hilo y varios. El camino final, sin embargo, usa solo aritmética entera.
Para un \(n\) fijo, el coste dominante es elevar una matriz \(3\times 3\) a la potencia \(m-2\), lo que requiere \(O(\log m)\) multiplicaciones matriciales. Como solo hay 30 valores de \(n\), el coste total es
$$O(30\log m)=O(\log m),$$
con memoria auxiliar \(O(1)\). La versión en C++ puede paralelizar los valores de \(n\), pero eso solo mejora el tiempo real de ejecución.
对每个 \(n\in\{1,\dots,30\}\)，令 \(a_n\) 为方程
$$x^3-2^n x^2+n=0$$
的最大实根。题目要求计算
$$\sum_{n=1}^{30}\left\lfloor a_n^{987654321}\right\rfloor \pmod{10^8}.$$
如果直接用浮点数去计算如此巨大的幂，既不稳定也没有必要。仓库里的 C++、Python 和 Java 解法都把问题改写成一个在 \(10^8\) 模意义下精确运行的线性递推。
记 \(c=2^n\)，并设 \(f(x)=x^3-cx^2+n\)。实现所依赖的关键事实是：这个三次多项式有三个实根，其中一个是接近 \(2^n\) 的大正根，另外两个都靠近原点。
因为
$$f(-1)=n-1-c<0,\qquad f(0)=n>0,$$
所以存在一个根 \(\gamma\in(-1,0)\)。又因为
$$f(1)=n+1-c\le 0,\qquad f(0)=n>0,$$
所以存在一个根 \(\beta\in(0,1]\)，且只有在 \(n=1\) 时才会出现 \(\beta=1\)。最后，
$$f(c)=n>0,\qquad f(c-1)=n-(c-1)^2\le 0,$$
因此最大实根 \(\alpha=a_n\) 落在 \((c-1,c)\) 内。于是三根满足
$$\gamma\in(-1,0),\qquad \beta\in(0,1],\qquad \alpha\in(2^n-1,2^n).$$
再由 Viète 关系可得
$$\alpha+\beta+\gamma=c,\qquad \alpha\beta+\alpha\gamma+\beta\gamma=0,\qquad \alpha\beta\gamma=-n.$$
定义
$$S_k=\alpha^k+\beta^k+\gamma^k.$$
每个根 \(r\in\{\alpha,\beta,\gamma\}\) 都满足
$$r^3=cr^2-n.$$
两边乘以 \(r^{k-3}\) 得到
$$r^k=cr^{k-1}-nr^{k-3}\qquad (k\ge 3).$$
对三个根求和，就得到代码真正使用的递推式：
$$\boxed{S_k=cS_{k-1}-nS_{k-3}\qquad (k\ge 3).}$$
初值同样很简单：
$$S_0=3,$$
$$S_1=\alpha+\beta+\gamma=c,$$
$$S_2=(\alpha+\beta+\gamma)^2-2(\alpha\beta+\alpha\gamma+\beta\gamma)=c^2.$$
这样，原问题就变成了一个三阶线性递推问题。
设 \(m\) 为奇数，并记小根的贡献为
$$\rho_m=\beta^m+\gamma^m.$$
由于 \(\gamma<0\) 且 \(m\) 为奇数，所以 \(\gamma^m<0\)。另一方面，
$$\beta+\gamma=c-\alpha,$$
而 \(\alpha\in(c-1,c)\) 说明
$$0<\beta+\gamma<1.$$
因此 \(\beta>|\gamma|\)。对奇数次幂，这意味着
$$\beta^m>|\gamma|^m,$$
从而
$$0<\rho_m=\beta^m-|\gamma|^m.$$
同时 \(\beta\le 1\) 且 \(|\gamma|<1\)，所以
$$\rho_m<1.$$
于是得到
$$0<\rho_m<1,$$
并且因为 \(\alpha^m=S_m-\rho_m\)，便有关键恒等式
$$\boxed{\left\lfloor \alpha^m\right\rfloor=\left\lfloor S_m-\rho_m\right\rfloor=S_m-1.}$$
这就是为什么正式解法完全不需要直接求 \(a_n^{987654321}\)。
因为递推阶数固定为 3，所以状态向量
$$\begin{bmatrix}S_k\\S_{k-1}\\S_{k-2}\end{bmatrix}$$
满足
$$\begin{bmatrix}S_k\\S_{k-1}\\S_{k-2}\end{bmatrix} = \begin{bmatrix} c & 0 & -n\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix}S_{k-1}\\S_{k-2}\\S_{k-3}\end{bmatrix}.$$
因此当 \(m\ge 2\) 时，
$$\begin{bmatrix}S_m\\S_{m-1}\\S_{m-2}\end{bmatrix} = M^{m-2} \begin{bmatrix}S_2\\S_1\\S_0\end{bmatrix}.$$
代码用二进制快速幂来计算 \(M^{m-2}\)，并且每一步都对 \(10^8\) 取模。在模运算中，系数 \(-n\) 会被写成
$$10^8-(n\bmod 10^8),$$
这正是实现里看到的非负写法。
取 \(n=2\)，此时 \(c=4\)。那么
$$S_0=3,\qquad S_1=4,\qquad S_2=16.$$
对于奇数指数 \(m=3\)，递推给出
$$S_3=4\cdot 16-2\cdot 3=58.$$
又因为 \(0<\beta^3+\gamma^3<1\)，所以
$$\left\lfloor a_2^3\right\rfloor=S_3-1=57.$$
C++ 版本在进入正式的大规模模运算之前，会先用这种小案例做数值核对。
三种语言的实现结构完全一致。首先，powMod 计算 \(c=2^n\bmod 10^8\)。然后，multiplyMatrix 和 powerMatrix 对 \(3\times 3\) 转移矩阵做快速幂。函数 computeNewtonSumMod 返回 \(S_m\bmod 10^8\)：当 \(m=0,1,2\) 时直接返回初值，更大的指数则通过矩阵幂得到。
接着，computeTermMod 利用 \(\lfloor a_n^m\rfloor\equiv S_m-1\pmod{10^8}\) 这一结论，solve 再把 \(n=1\) 到 \(30\) 的结果累加起来。较长的 C++ 文件还包含几项验证逻辑：检查题目中的样例 \(\lfloor a_2^2\rfloor=14\)，比较矩阵递推与迭代递推，验证小规模奇数幂下的取整恒等式，以及测试多线程结果是否一致。不过真正的快速路径始终只使用整数运算。
对固定的 \(n\) 来说，主要成本是把 \(3\times 3\) 矩阵提升到 \(m-2\) 次幂，这需要 \(O(\log m)\) 次矩阵乘法。题目只需要处理 30 个 \(n\)，所以总时间复杂度为
$$O(30\log m)=O(\log m),$$
额外空间复杂度为 \(O(1)\)。C++ 版本可以把不同的 \(n\) 并行计算，但这只影响实际运行时间，不改变复杂度级别。
Для каждого \(n\in\{1,\dots,30\}\) обозначим через \(a_n\) наибольший действительный корень уравнения
$$x^3-2^n x^2+n=0.$$
Нужно вычислить
$$\sum_{n=1}^{30}\left\lfloor a_n^{987654321}\right\rfloor \pmod{10^8}.$$
Напрямую поднимать корни в такую огромную степень с плавающей точкой было бы и медленно, и ненадежно. Локальные решения на C++, Python и Java сводят задачу к точной линейной рекурсии по модулю \(10^8\).
Положим \(c=2^n\) и \(f(x)=x^3-cx^2+n\). Ключевой факт состоит в том, что у этого кубического многочлена три действительных корня: один большой положительный и два малых около нуля.
Имеем
$$f(-1)=n-1-c<0,\qquad f(0)=n>0,$$
значит, существует корень \(\gamma\in(-1,0)\). Далее,
$$f(1)=n+1-c\le 0,\qquad f(0)=n>0,$$
поэтому существует корень \(\beta\in(0,1]\), причем \(\beta=1\) только при \(n=1\). Наконец,
$$f(c)=n>0,\qquad f(c-1)=n-(c-1)^2\le 0,$$
следовательно, наибольший корень \(\alpha=a_n\) лежит в интервале \((c-1,c)\). Итак,
$$\gamma\in(-1,0),\qquad \beta\in(0,1],\qquad \alpha\in(2^n-1,2^n).$$
По формулам Виета:
$$\alpha+\beta+\gamma=c,\qquad \alpha\beta+\alpha\gamma+\beta\gamma=0,\qquad \alpha\beta\gamma=-n.$$
Введем
$$S_k=\alpha^k+\beta^k+\gamma^k.$$
Каждый корень \(r\in\{\alpha,\beta,\gamma\}\) удовлетворяет равенству
$$r^3=cr^2-n.$$
Умножая его на \(r^{k-3}\), получаем
$$r^k=cr^{k-1}-nr^{k-3}\qquad (k\ge 3).$$
Суммирование по трем корням дает рекурсию, которая и реализована в коде:
$$\boxed{S_k=cS_{k-1}-nS_{k-3}\qquad (k\ge 3).}$$
Начальные значения таковы:
$$S_0=3,$$
$$S_1=\alpha+\beta+\gamma=c,$$
$$S_2=(\alpha+\beta+\gamma)^2-2(\alpha\beta+\alpha\gamma+\beta\gamma)=c^2.$$
Тем самым исходная задача сведена к линейной рекурсии третьего порядка.
Пусть \(m\) нечетно, и обозначим вклад малых корней через
$$\rho_m=\beta^m+\gamma^m.$$
Так как \(\gamma<0\) и \(m\) нечетно, имеем \(\gamma^m<0\). Кроме того,
$$\beta+\gamma=c-\alpha,$$
а из \(\alpha\in(c-1,c)\) следует
$$0<\beta+\gamma<1.$$
Значит, \(\beta>|\gamma|\). Для нечетной степени получаем
$$\beta^m>|\gamma|^m,$$
и потому
$$0<\rho_m=\beta^m-|\gamma|^m.$$
С другой стороны, \(\beta\le 1\) и \(|\gamma|<1\), следовательно,
$$\rho_m<1.$$
Итак,
$$0<\rho_m<1,$$
а поскольку \(\alpha^m=S_m-\rho_m\), получаем основное тождество
$$\boxed{\left\lfloor \alpha^m\right\rfloor=\left\lfloor S_m-\rho_m\right\rfloor=S_m-1.}$$
Именно поэтому быстрый путь решения не вычисляет \(a_n^{987654321}\) напрямую.
Рекурсия имеет фиксированный порядок 3, поэтому вектор состояния
$$\begin{bmatrix}S_k\\S_{k-1}\\S_{k-2}\end{bmatrix}$$
эволюционирует по правилу
$$\begin{bmatrix}S_k\\S_{k-1}\\S_{k-2}\end{bmatrix} = \begin{bmatrix} c & 0 & -n\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix}S_{k-1}\\S_{k-2}\\S_{k-3}\end{bmatrix}.$$
Следовательно, при \(m\ge 2\)
$$\begin{bmatrix}S_m\\S_{m-1}\\S_{m-2}\end{bmatrix} = M^{m-2} \begin{bmatrix}S_2\\S_1\\S_0\end{bmatrix}.$$
Программа вычисляет эту степень бинарным возведением, каждый раз сокращая результат по модулю \(10^8\). Коэффициент \(-n\) в модульной арифметике хранится как
$$10^8-(n\bmod 10^8),$$
поэтому в исходниках он записан без отрицательных чисел.
Возьмем \(n=2\), тогда \(c=4\). Получаем
$$S_0=3,\qquad S_1=4,\qquad S_2=16.$$
Для нечетного показателя \(m=3\) рекурсия дает
$$S_3=4\cdot 16-2\cdot 3=58.$$
Так как \(0<\beta^3+\gamma^3<1\), отсюда следует
$$\left\lfloor a_2^3\right\rfloor=S_3-1=57.$$
В C++-версии именно такие малые проверки используются как валидация перед основным модульным вычислением.
Во всех трех языках логика одна и та же. Сначала функция powMod вычисляет \(c=2^n\bmod 10^8\). Затем multiplyMatrix и powerMatrix возводят переходную матрицу \(3\times 3\) в степень \(m-2\). Функция computeNewtonSumMod возвращает \(S_m\bmod 10^8\): случаи \(m=0,1,2\) обрабатываются напрямую, для больших показателей используется матричное возведение.
После этого computeTermMod применяет тождество \(\lfloor a_n^m\rfloor\equiv S_m-1\pmod{10^8}\), а solve суммирует значения по \(n=1,\dots,30\). Более длинный файл на C++ также содержит проверки: пример из условия \(\lfloor a_2^2\rfloor=14\), сравнение матричной и итеративной рекурсий, численную проверку тождества пола на малых случаях и тест согласованности однопоточного и многопоточного режимов. Но сам быстрый путь полностью целочисленный.
Для фиксированного \(n\) основная стоимость состоит в возведении матрицы \(3\times 3\) в степень \(m-2\), что требует \(O(\log m)\) матричных умножений. Так как значений \(n\) всего 30, итоговая сложность равна
$$O(30\log m)=O(\log m),$$
а дополнительная память составляет \(O(1)\). Версия на C++ может распараллелить независимые значения \(n\), но это меняет только практическое время работы.
لكل \(n\in\{1,\dots,30\}\)، ليكن \(a_n\) أكبر جذر حقيقي للمعادلة
$$x^3-2^n x^2+n=0.$$
المطلوب حساب
$$\sum_{n=1}^{30}\left\lfloor a_n^{987654321}\right\rfloor \pmod{10^8}.$$
رفع هذه الجذور إلى أس هائل مباشرة باستخدام الأعداد العائمة ليس خيارًا جيدًا. الحلول المحلية في C++ وPython وJava تحوّل المسألة إلى علاقة عودية خطية دقيقة تعمل مباشرة تحت المودولو \(10^8\).
لنكتب \(c=2^n\) و\(f(x)=x^3-cx^2+n\). الفكرة الأساسية في التنفيذ أن هذا كثير الحدود التكعيبي يملك ثلاثة جذور حقيقية: جذرًا موجبًا كبيرًا، وجذرين صغيرين قريبين من الصفر.
لدينا
$$f(-1)=n-1-c<0,\qquad f(0)=n>0,$$
ومن ثم يوجد جذر \(\gamma\in(-1,0)\). كذلك
$$f(1)=n+1-c\le 0,\qquad f(0)=n>0,$$
لذلك يوجد جذر \(\beta\in(0,1]\)، وتكون \(\beta=1\) فقط عندما \(n=1\). وأخيرًا
$$f(c)=n>0,\qquad f(c-1)=n-(c-1)^2\le 0,$$
ولهذا يقع أكبر جذر \(\alpha=a_n\) داخل الفترة \((c-1,c)\). إذن
$$\gamma\in(-1,0),\qquad \beta\in(0,1],\qquad \alpha\in(2^n-1,2^n).$$
ومن علاقات فييتا نحصل على
$$\alpha+\beta+\gamma=c,\qquad \alpha\beta+\alpha\gamma+\beta\gamma=0,\qquad \alpha\beta\gamma=-n.$$
نعرّف
$$S_k=\alpha^k+\beta^k+\gamma^k.$$
كل جذر \(r\in\{\alpha,\beta,\gamma\}\) يحقق
$$r^3=cr^2-n.$$
وبعد الضرب في \(r^{k-3}\) نحصل على
$$r^k=cr^{k-1}-nr^{k-3}\qquad (k\ge 3).$$
وبالجمع على الجذور الثلاثة تظهر نفس العلاقة العودية الموجودة في الشيفرة:
$$\boxed{S_k=cS_{k-1}-nS_{k-3}\qquad (k\ge 3).}$$
أما القيم الابتدائية فهي
$$S_0=3,$$
$$S_1=\alpha+\beta+\gamma=c,$$
$$S_2=(\alpha+\beta+\gamma)^2-2(\alpha\beta+\alpha\gamma+\beta\gamma)=c^2.$$
بهذا تتحول المسألة كلها إلى علاقة عودية خطية من الرتبة الثالثة.
لنفرض أن \(m\) فردي، ولنعرف مساهمة الجذرين الصغيرين بالكمية
$$\rho_m=\beta^m+\gamma^m.$$
بما أن \(\gamma<0\) و\(m\) فردي، فإن \(\gamma^m<0\). كذلك لدينا
$$\beta+\gamma=c-\alpha,$$
ومع \(\alpha\in(c-1,c)\) ينتج
$$0<\beta+\gamma<1.$$
إذًا \(\beta>|\gamma|\). وللأس الفردي نحصل على
$$\beta^m>|\gamma|^m,$$
ومن ثم
$$0<\rho_m=\beta^m-|\gamma|^m.$$
وفي الوقت نفسه \(\beta\le 1\) و\(|\gamma|<1\)، ولذلك
$$\rho_m<1.$$
إذن
$$0<\rho_m<1,$$
وبما أن \(\alpha^m=S_m-\rho_m\)، نحصل على الهوية الأساسية
$$\boxed{\left\lfloor \alpha^m\right\rfloor=\left\lfloor S_m-\rho_m\right\rfloor=S_m-1.}$$
ولهذا لا يحتاج المسار السريع في الحل إلى حساب \(a_n^{987654321}\) مباشرة.
بما أن العلاقة العودية من الرتبة 3، فإن متجه الحالة
$$\begin{bmatrix}S_k\\S_{k-1}\\S_{k-2}\end{bmatrix}$$
يتطور وفقًا لـ
$$\begin{bmatrix}S_k\\S_{k-1}\\S_{k-2}\end{bmatrix} = \begin{bmatrix} c & 0 & -n\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix}S_{k-1}\\S_{k-2}\\S_{k-3}\end{bmatrix}.$$
ومن ثم عندما \(m\ge 2\)،
$$\begin{bmatrix}S_m\\S_{m-1}\\S_{m-2}\end{bmatrix} = M^{m-2} \begin{bmatrix}S_2\\S_1\\S_0\end{bmatrix}.$$
تحسب الشيفرة هذه القوة بالرفع الثنائي، مع أخذ كل عملية تحت المودولو \(10^8\). ولهذا يُخزَّن المعامل \(-n\) في الصورة
$$10^8-(n\bmod 10^8),$$
بدلًا من استعمال عدد سالب داخل المصفوفة.
خذ \(n=2\)، وعندها يكون \(c=4\). إذن
$$S_0=3,\qquad S_1=4,\qquad S_2=16.$$
وللأس الفردي \(m=3\) تعطي العلاقة العودية
$$S_3=4\cdot 16-2\cdot 3=58.$$
وبما أن \(0<\beta^3+\gamma^3<1\)، نحصل على
$$\left\lfloor a_2^3\right\rfloor=S_3-1=57.$$
نسخة C++ تستخدم هذا النوع من الحالات الصغيرة كفحوص تحقق قبل الاعتماد على المسار السريع الكامل.
الإصدارات الثلاثة تستخدم البنية نفسها. أولًا تحسب الدالة powMod القيمة \(c=2^n\bmod 10^8\). بعد ذلك ترفع الدالتان multiplyMatrix وpowerMatrix مصفوفة الانتقال \(3\times 3\) إلى القوة \(m-2\). وترجع الدالة computeNewtonSumMod القيمة \(S_m\bmod 10^8\)، مع معالجة الحالات \(m=0,1,2\) مباشرة، واستعمال أس المصفوفة لبقية الحالات.
ثم تطبق computeTermMod الهوية \(\lfloor a_n^m\rfloor\equiv S_m-1\pmod{10^8}\)، وتقوم solve بجمع القيم من \(n=1\) إلى \(30\). الملف الأطول في C++ يحتوي أيضًا على فحوص تحقق: مثال المسألة \(\lfloor a_2^2\rfloor=14\)، مقارنة بين العلاقة العودية بالمصفوفة والنسخة التكرارية، فحص عددي لهوية الأرضية في أمثلة صغيرة، واختبار اتساق التنفيذ أحادي الخيط ومتعدد الخيوط. لكن المسار النهائي نفسه يعتمد فقط على حسابات صحيحة.
لكل قيمة ثابتة من \(n\)، فإن الكلفة المهيمنة هي رفع مصفوفة \(3\times 3\) إلى القوة \(m-2\)، وهذا يحتاج إلى \(O(\log m)\) عملية ضرب مصفوفات. وبما أن عدد قيم \(n\) يساوي 30 فقط، فالتعقيد الكلي هو
$$O(30\log m)=O(\log m),$$
مع ذاكرة إضافية \(O(1)\). نسخة C++ يمكنها توزيع قيم \(n\) المستقلة على عدة خيوط، لكن هذا يحسن زمن التنفيذ العملي فقط.