Let \(r\) be the irrational base used in the problem. For each positive integer \(n\), we consider its greedy representation as a sum of distinct powers of \(r\), and we write \(\ell(n)\) for the number of selected powers. The quantity to compute is
$$S(m)=\sum_{j=1}^{m}\ell(j^2),\qquad m=5{,}000{,}000.$$
The challenge is that the base is irrational, so the implementation must make millions of precise comparisons and subtractions without letting floating-point error corrupt the greedy choices.
The implementations rely on one algebraic identity for the base and one numerical device for comparing powers quickly.
The base is
$$r=\frac{1+\sqrt[3]{\frac{29-3\sqrt{93}}{2}}+\sqrt[3]{\frac{29+3\sqrt{93}}{2}}}{3}\approx 1.465571231876768.$$
This is the unique real root of
$$x^3-x^2-1=0,$$
so it satisfies
$$r^3=r^2+1.$$
Multiplying by \(r^{e-2}\) gives the recurrence
$$r^{e+1}=r^e+r^{e-2}.$$
That recurrence explains the combinatorial shape of the greedy expansion.
Suppose the greedy process has chosen the largest admissible power \(r^e\le n\). If the residual is \(R=n-r^e\), then \(n<r^{e+1}\), hence
$$0\le R<r^{e+1}-r^e=r^{e-2}.$$
Therefore the next selected power cannot be \(r^{e-1}\) or \(r^{e-2}\); its exponent must be at most \(e-3\). Repeating the same argument at every step yields the greedy form used by the implementations:
$$n=\sum_{t=1}^{\ell(n)} r^{e_t},\qquad e_1>e_2>\cdots,\qquad e_{t+1}\le e_t-3.$$
So after one term is chosen, the next search can start three exponents lower and continue downward only if the residual is still smaller than that first candidate.
Take \(n=4\). Since
$$r^3\approx 3.147899<4<r^4\approx 4.613470,$$
the first greedy term is \(r^3\). The remaining amount is about \(0.852101\), so the next admissible term is \(r^{-1}\approx 0.682328\). Continuing in the same way gives
$$4=r^3+r^{-1}+r^{-5}+r^{-10}.$$
Numerically,
$$3.147899+0.682328+0.147899+0.021874\approx 4.$$
The decimal values only illustrate the greedy choices; the equality itself is exact because all terms are powers of the algebraic number \(r\). Hence \(\ell(4)=4\).
Directly comparing irrational numbers inside the inner loop would be both slow and fragile. Instead, the implementations precompute each power in the form
$$r^e=a_e+\frac{b_e}{M}+\frac{c_e}{M^2}+O(M^{-3}),\qquad M=10^{17},$$
where \(a_e\), \(b_e\), and \(c_e\) are integers obtained from a high-precision evaluation of \(r^e\). Residuals are stored in the same three-level format. To decide whether a power fits into the current residual, the implementation only needs a lexicographic comparison of the triples
$$\left(a_e,b_e,c_e\right),\qquad \left(R_1,R_2,R_3\right).$$
After each subtraction, borrow propagation normalizes the three components exactly as in arithmetic with base \(M\).
For every square \(j^2\), the algorithm finds the largest precomputed power below it, repeatedly subtracts the largest admissible lower power, and counts how many terms were used. That count is \(\ell(j^2)\), so the final answer is simply
$$S(m)=\sum_{j=1}^{m}\ell(j^2).$$
The implementations verify two checkpoints before the full run:
$$S(10)=61,\qquad S(1000)=19403.$$
These values confirm that the greedy representation and the fixed-point comparisons are aligned.
The C++ and Java implementations first evaluate the algebraic base with high decimal precision and build a table of powers over a finite exponent window wide enough for the target computation. Each stored power is split into three integer layers so that the inner greedy loop can avoid arbitrary-precision arithmetic.
For each square, the implementation locates the leading power, initializes the residual in the same three-layer format, then repeatedly searches downward for the next admissible term, subtracts it with borrow handling, and increments the representation length. Because the squares increase with \(j\), the search for the leading exponent only moves forward through the table. The Python implementation delegates to the same compiled algorithm, so all three language versions use the same greedy decomposition and the same checkpoints.
Let \(W=E_{\max}-E_{\min}+1\) denote the size of the precomputed exponent window. Building the table costs \(O(W)\) high-precision steps and \(O(W)\) memory. Over the whole sweep \(j=1,\dots,m\), the forward search for the leading exponent is monotone, so it contributes \(O(W+m)\) total work. The dominant part is the greedy subtraction itself, which is proportional to the total number of selected terms:
$$O\left(W+m+\sum_{j=1}^{m}\ell(j^2)\right).$$
Since \(W\) is fixed in the implementations, memory usage is effectively constant with respect to \(m\), and the running time is essentially linear in the total output length of the greedy expansions.
Sei \(r\) die im Problem verwendete irrationale Basis. Für jede positive ganze Zahl \(n\) betrachten wir ihre greedy konstruierte Darstellung als Summe verschiedener Potenzen von \(r\); mit \(\ell(n)\) bezeichnen wir die Anzahl der benutzten Potenzen. Gesucht ist
$$S(m)=\sum_{j=1}^{m}\ell(j^2),\qquad m=5{,}000{,}000.$$
Die Schwierigkeit besteht darin, dass die Basis irrational ist. Deshalb muss die Implementierung Millionen präziser Vergleiche und Subtraktionen durchführen, ohne dass Rundungsfehler die greedy Auswahl verfälschen.
Die Implementierungen stützen sich auf eine algebraische Identität der Basis und auf eine feste numerische Darstellung der Potenzen.
Die Basis ist
$$r=\frac{1+\sqrt[3]{\frac{29-3\sqrt{93}}{2}}+\sqrt[3]{\frac{29+3\sqrt{93}}{2}}}{3}\approx 1.465571231876768.$$
Sie ist die eindeutige reelle Nullstelle von
$$x^3-x^2-1=0,$$
also gilt
$$r^3=r^2+1.$$
Nach Multiplikation mit \(r^{e-2}\) folgt die Rekursion
$$r^{e+1}=r^e+r^{e-2}.$$
Genau diese Beziehung erklärt die Struktur der greedy Darstellung.
Angenommen, der greedy Schritt wählt die größte zulässige Potenz \(r^e\le n\). Für den Rest \(R=n-r^e\) gilt wegen \(n<r^{e+1}\)
$$0\le R<r^{e+1}-r^e=r^{e-2}.$$
Damit kann der nächste Summand weder \(r^{e-1}\) noch \(r^{e-2}\) sein; sein Exponent ist höchstens \(e-3\). Wiederholt man dieses Argument, erhält man die von den Implementierungen verwendete greedy Form
$$n=\sum_{t=1}^{\ell(n)} r^{e_t},\qquad e_1>e_2>\cdots,\qquad e_{t+1}\le e_t-3.$$
Deshalb startet die Suche nach dem nächsten Kandidaten immer drei Exponenten tiefer und läuft nur dann weiter nach unten, wenn auch dieser Kandidat noch zu groß ist.
Betrachte \(n=4\). Wegen
$$r^3\approx 3.147899<4<r^4\approx 4.613470$$
ist der erste greedy Summand \(r^3\). Der verbleibende Rest ist ungefähr \(0.852101\), also ist der nächste zulässige Summand \(r^{-1}\approx 0.682328\). Führt man den Prozess fort, erhält man
$$4=r^3+r^{-1}+r^{-5}+r^{-10}.$$
Numerisch ist das
$$3.147899+0.682328+0.147899+0.021874\approx 4.$$
Die Dezimalzahlen illustrieren nur die greedy Auswahl; die Gleichheit selbst ist exakt, weil alle Terme Potenzen der algebraischen Zahl \(r\) sind. Also ist \(\ell(4)=4\).
Ein direkter Vergleich irrationaler Zahlen in der inneren Schleife wäre langsam und fehleranfällig. Daher werden die Potenzen vorab in der Form
$$r^e=a_e+\frac{b_e}{M}+\frac{c_e}{M^2}+O(M^{-3}),\qquad M=10^{17},$$
gespeichert, wobei \(a_e\), \(b_e\) und \(c_e\) ganze Zahlen aus einer hochpräzisen Berechnung von \(r^e\) sind. Der aktuelle Rest wird im selben dreistufigen Format geführt. Um zu prüfen, ob eine Potenz in den Rest passt, genügt ein lexikographischer Vergleich der Tripel
$$\left(a_e,b_e,c_e\right),\qquad \left(R_1,R_2,R_3\right).$$
Nach jeder Subtraktion normalisiert eine Borrow-Propagation die drei Ebenen genau wie bei einer Subtraktion zur Basis \(M\).
Für jedes Quadrat \(j^2\) sucht der Algorithmus die größte vorab berechnete Potenz darunter, subtrahiert dann wiederholt die größte zulässige kleinere Potenz und zählt die verwendeten Summanden. Diese Anzahl ist \(\ell(j^2)\), also ist die gesuchte Endgröße
$$S(m)=\sum_{j=1}^{m}\ell(j^2).$$
Vor dem vollständigen Lauf prüfen die Implementierungen zwei Kontrollwerte:
$$S(10)=61,\qquad S(1000)=19403.$$
Damit wird bestätigt, dass greedy Darstellung und Festkomma-Vergleiche korrekt zusammenarbeiten.
Die C++- und Java-Implementierungen berechnen zunächst die algebraische Basis mit hoher Dezimalpräzision und bauen dann eine Potenztabelle über ein endliches Exponentenfenster auf, das für die Zielrechnung ausreicht. Jede Potenz wird in drei ganzzahlige Ebenen zerlegt, sodass die innere greedy Schleife ohne beliebig genaue Arithmetik auskommt.
Für jedes Quadrat bestimmt die Implementierung die führende Potenz, initialisiert den Rest im selben Dreiebenen-Format und sucht dann wiederholt abwärts nach dem nächsten zulässigen Summanden, subtrahiert ihn mit Borrow-Behandlung und erhöht die Darstellungslänge. Weil die Quadrate mit \(j\) wachsen, bewegt sich die Suche nach dem Start-Exponenten nur vorwärts durch die Tabelle. Die Python-Implementierung delegiert an denselben kompilierten Algorithmus, daher verwenden alle drei Sprachversionen dieselbe greedy Zerlegung und dieselben Kontrollwerte.
Sei \(W=E_{\max}-E_{\min}+1\) die Größe des vorab berechneten Exponentenfensters. Der Aufbau der Tabelle kostet \(O(W)\) hochpräzise Schritte und \(O(W)\) Speicher. Über den gesamten Bereich \(j=1,\dots,m\) ist die Suche nach dem führenden Exponenten monoton und benötigt daher insgesamt \(O(W+m)\) Arbeit. Dominant ist die greedy Subtraktion selbst; ihr Aufwand ist proportional zur Gesamtzahl der ausgewählten Terme:
$$O\left(W+m+\sum_{j=1}^{m}\ell(j^2)\right).$$
Da \(W\) in den Implementierungen fest ist, ist der Speicherverbrauch bezüglich \(m\) praktisch konstant, und die Laufzeit ist im Wesentlichen linear in der gesamten Ausgabelänge der greedy Darstellungen.
\(r\), problemde kullanılan irrasyonel taban olsun. Her pozitif tamsayı \(n\) için, \(n\)'yi \(r\)'nin farklı kuvvetlerinin greedy toplamı olarak yazıyoruz; kullanılan terim sayısını \(\ell(n)\) ile gösterelim. Hesaplanması gereken büyüklük
$$S(m)=\sum_{j=1}^{m}\ell(j^2),\qquad m=5{,}000{,}000.$$
Asıl zorluk, tabanın irrasyonel olmasıdır. Bu yüzden uygulama, greedy seçimleri bozmayacak kadar güvenilir biçimde milyonlarca karşılaştırma ve çıkarma yapmak zorundadır.
Uygulamalar hem tabanın cebirsel bir özelliğini hem de kuvvetleri hızlı karşılaştırmaya yarayan sabit-nokta benzeri bir gösterimi kullanır.
Taban
$$r=\frac{1+\sqrt[3]{\frac{29-3\sqrt{93}}{2}}+\sqrt[3]{\frac{29+3\sqrt{93}}{2}}}{3}\approx 1.465571231876768$$
şeklindedir. Bu sayı
$$x^3-x^2-1=0$$
denkleminin tek gerçek köküdür; dolayısıyla
$$r^3=r^2+1$$
eşitliği sağlanır. Bunu \(r^{e-2}\) ile çarparsak
$$r^{e+1}=r^e+r^{e-2}$$
elde edilir. Greedy açılımın yapısını belirleyen temel ilişki budur.
Greedy adımda seçilen en büyük uygun kuvvet \(r^e\le n\) olsun. Kalan \(R=n-r^e\) ise, \(n<r^{e+1}\) olduğundan
$$0\le R<r^{e+1}-r^e=r^{e-2}.$$
Böylece bir sonraki terim \(r^{e-1}\) ya da \(r^{e-2}\) olamaz; üssü en fazla \(e-3\) olur. Bu argüman tekrarlandığında uygulamaların kullandığı greedy biçim ortaya çıkar:
$$n=\sum_{t=1}^{\ell(n)} r^{e_t},\qquad e_1>e_2>\cdots,\qquad e_{t+1}\le e_t-3.$$
Bu nedenle her seçimden sonra arama doğrudan üç üs aşağıdan başlatılır; gerekirse oradan da daha küçük kuvvetlere inilir.
\(n=4\) için
$$r^3\approx 3.147899<4<r^4\approx 4.613470$$
olduğu için ilk greedy terim \(r^3\)'tür. Kalan yaklaşık \(0.852101\) olur; bu yüzden bir sonraki uygun terim \(r^{-1}\approx 0.682328\)'dir. Süreç devam ettirilince
$$4=r^3+r^{-1}+r^{-5}+r^{-10}$$
bulunur. Sayısal olarak
$$3.147899+0.682328+0.147899+0.021874\approx 4.$$
Ondalık değerler sadece greedy seçimlerin nedenini gösterir; eşitliğin kendisi tamdır, çünkü bütün terimler cebirsel sayı \(r\)'nin kuvvetleridir. Dolayısıyla \(\ell(4)=4\).
İç döngüde irrasyonel sayıları doğrudan karşılaştırmak hem yavaş hem de riskli olurdu. Bunun yerine her kuvvet
$$r^e=a_e+\frac{b_e}{M}+\frac{c_e}{M^2}+O(M^{-3}),\qquad M=10^{17}$$
şeklinde önceden saklanır. Burada \(a_e\), \(b_e\), \(c_e\), \(r^e\)'nin yüksek hassasiyetli hesabından elde edilen tamsayılardır. Kalan da aynı üç seviyeli formatta tutulur. Bir kuvvetin kalana sığıp sığmadığını anlamak için
$$\left(a_e,b_e,c_e\right),\qquad \left(R_1,R_2,R_3\right)$$
üçlülerini lexicographic olarak karşılaştırmak yeterlidir. Her çıkarmadan sonra yapılan borrow yayılımı, üç seviyeyi taban \(M\) aritmetiğinde olduğu gibi normalize eder.
Her \(j^2\) karesi için algoritma önce altındaki en büyük önhesaplı kuvveti bulur, sonra uygun olan en büyük daha küçük kuvvetleri birer birer çıkarır ve kullanılan terim sayısını sayar. Bu sayı \(\ell(j^2)\) olduğundan sonuç
$$S(m)=\sum_{j=1}^{m}\ell(j^2)$$
olur. Tam çalışmadan önce iki kontrol değeri doğrulanır:
$$S(10)=61,\qquad S(1000)=19403.$$
Bu kontrol noktaları greedy temsilin ve sabit-nokta karşılaştırmalarının uyumlu olduğunu gösterir.
C++ ve Java uygulamaları önce cebirsel tabanı yüksek ondalık hassasiyetle hesaplar, ardından hedef hesap için yeterli genişlikte sonlu bir üs penceresi üzerinde kuvvet tablosu kurar. Her kuvvet üç tamsayı katmanına ayrılır; böylece iç greedy döngü keyfi hassasiyetli aritmetik kullanmak zorunda kalmaz.
Her kare için uygulama öndeki kuvveti bulur, kalanı aynı üç katmanlı formatta başlatır, sonra bir sonraki uygun terimi bulmak için aşağı doğru tarar, çıkarmayı borrow düzeltmesiyle yapar ve temsil uzunluğunu artırır. Kareler \(j\) ile büyüdüğü için başlangıç üssünü bulma işlemi tablo içinde sadece ileri doğru hareket eder. Python uygulaması da aynı derlenmiş algoritmaya delege ettiği için üç dilde de greedy ayrışım ve kontrol noktaları aynıdır.
\(W=E_{\max}-E_{\min}+1\), önhesaplanan üs penceresinin boyutu olsun. Tablo kurma maliyeti \(O(W)\) yüksek hassasiyetli adım ve \(O(W)\) bellektir. Tüm \(j=1,\dots,m\) aralığında öndeki üssü bulma araması monoton ilerlediği için toplam katkısı \(O(W+m)\) olur. Baskın maliyet greedy çıkarma sürecidir ve toplam seçilen terim sayısı ile orantılıdır:
$$O\left(W+m+\sum_{j=1}^{m}\ell(j^2)\right).$$
\(W\) uygulamalarda sabit tutulduğu için bellek kullanımı \(m\)'e göre pratikte sabittir; çalışma süresi ise temelde greedy açılımların toplam çıktı uzunluğu ile lineerdir.
Sea \(r\) la base irracional usada en el problema. Para cada entero positivo \(n\), se considera su representación voraz como suma de potencias distintas de \(r\), y \(\ell(n)\) denota el número de potencias seleccionadas. Lo que hay que calcular es
$$S(m)=\sum_{j=1}^{m}\ell(j^2),\qquad m=5{,}000{,}000.$$
La dificultad es que la base es irracional. Por ello, la implementación debe hacer millones de comparaciones y restas exactas en la práctica, sin que el error de coma flotante altere las decisiones voraces.
Las implementaciones se apoyan en una identidad algebraica simple para la base y en una representación numérica estable para las potencias.
La base es
$$r=\frac{1+\sqrt[3]{\frac{29-3\sqrt{93}}{2}}+\sqrt[3]{\frac{29+3\sqrt{93}}{2}}}{3}\approx 1.465571231876768.$$
Es la única raíz real de
$$x^3-x^2-1=0,$$
así que satisface
$$r^3=r^2+1.$$
Multiplicando por \(r^{e-2}\) se obtiene la recurrencia
$$r^{e+1}=r^e+r^{e-2}.$$
Esa recurrencia es la columna vertebral algebraica del sistema de numeración.
Supongamos que el proceso voraz escoge la mayor potencia admisible \(r^e\le n\). Si \(R=n-r^e\) es el residuo, entonces como \(n<r^{e+1}\) se cumple
$$0\le R<r^{e+1}-r^e=r^{e-2}.$$
Por lo tanto, el siguiente término no puede ser \(r^{e-1}\) ni \(r^{e-2}\); su exponente tiene que ser como mucho \(e-3\). Repitiendo el mismo razonamiento se obtiene la forma voraz usada por las implementaciones:
$$n=\sum_{t=1}^{\ell(n)} r^{e_t},\qquad e_1>e_2>\cdots,\qquad e_{t+1}\le e_t-3.$$
Por eso, después de elegir un término, la búsqueda del siguiente empieza tres posiciones más abajo y solo sigue descendiendo si ese primer candidato todavía es demasiado grande.
Tomemos \(n=4\). Como
$$r^3\approx 3.147899<4<r^4\approx 4.613470,$$
el primer término voraz es \(r^3\). El residuo es aproximadamente \(0.852101\), así que el siguiente término admisible es \(r^{-1}\approx 0.682328\). Continuando de la misma manera se obtiene
$$4=r^3+r^{-1}+r^{-5}+r^{-10}.$$
Numéricamente,
$$3.147899+0.682328+0.147899+0.021874\approx 4.$$
Los valores decimales solo ilustran las elecciones voraces; la igualdad es exacta porque todos los sumandos son potencias del número algebraico \(r\). Por tanto, \(\ell(4)=4\).
Comparar números irracionales directamente en el bucle interno sería lento y delicado. En su lugar, cada potencia se precalcula en la forma
$$r^e=a_e+\frac{b_e}{M}+\frac{c_e}{M^2}+O(M^{-3}),\qquad M=10^{17},$$
donde \(a_e\), \(b_e\) y \(c_e\) son enteros obtenidos a partir de una evaluación de alta precisión de \(r^e\). El residuo se guarda en el mismo formato de tres niveles. Para decidir si una potencia cabe en el residuo actual, basta comparar lexicográficamente los triples
$$\left(a_e,b_e,c_e\right),\qquad \left(R_1,R_2,R_3\right).$$
Después de cada resta, la propagación de préstamos normaliza las tres capas igual que en una resta en base \(M\).
Para cada cuadrado \(j^2\), el algoritmo encuentra la mayor potencia precalculada que no lo supera, luego va restando repetidamente la mayor potencia menor todavía admisible y cuenta cuántos términos usa. Ese conteo es \(\ell(j^2)\), así que el resultado final es
$$S(m)=\sum_{j=1}^{m}\ell(j^2).$$
Antes de ejecutar el caso completo, las implementaciones verifican dos puntos de control:
$$S(10)=61,\qquad S(1000)=19403.$$
Esos valores confirman que la representación voraz y las comparaciones en punto fijo están coordinadas correctamente.
Las implementaciones en C++ y Java evalúan primero la base algebraica con alta precisión decimal y construyen una tabla de potencias en una ventana finita de exponentes suficientemente amplia para el cálculo objetivo. Cada potencia se divide en tres capas enteras para que el bucle voraz interno no necesite aritmética multiprecisión.
Para cada cuadrado, la implementación localiza la potencia líder, inicializa el residuo con el mismo formato de tres capas y luego busca hacia abajo el siguiente término admisible, lo resta con manejo de préstamos y aumenta la longitud de la representación. Como los cuadrados crecen con \(j\), la búsqueda del exponente inicial solo avanza hacia delante a lo largo de la tabla. La implementación en Python delega en el mismo algoritmo compilado, de modo que las tres versiones comparten la misma descomposición voraz y los mismos puntos de control.
Sea \(W=E_{\max}-E_{\min}+1\) el tamaño de la ventana de exponentes precalculada. Construir la tabla cuesta \(O(W)\) pasos de alta precisión y \(O(W)\) memoria. A lo largo de todo el barrido \(j=1,\dots,m\), la búsqueda hacia delante del exponente líder es monótona, así que aporta \(O(W+m)\) trabajo total. El coste dominante es la propia descomposición voraz, proporcional al número total de términos elegidos:
$$O\left(W+m+\sum_{j=1}^{m}\ell(j^2)\right).$$
Como \(W\) es fijo en las implementaciones, el uso de memoria es efectivamente constante respecto de \(m\), y el tiempo de ejecución es esencialmente lineal en la longitud total de salida de las expansiones voraces.
设 \(r\) 是本题使用的无理数进位基数。对每个正整数 \(n\)，我们考虑它写成若干个不同 \(r\) 的幂之和时的贪心表示，并用 \(\ell(n)\) 表示所选幂的个数。题目要求计算
$$S(m)=\sum_{j=1}^{m}\ell(j^2),\qquad m=5{,}000{,}000.$$
真正的难点不在于平方本身，而在于基数 \(r\) 是无理数。实现必须在数百万次贪心选择中持续做出可靠比较，既不能让浮点误差改变选择顺序，也不能让高精度运算拖慢整个过程。
实现所依赖的核心只有两件事：第一，基数 \(r\) 满足一个非常简单的三次方程；第二，所有需要的幂都可以先压缩成稳定的三层定点表示，再在内层循环中只做整数比较与整数减法。
本题中的基数为
$$r=\frac{1+\sqrt[3]{\frac{29-3\sqrt{93}}{2}}+\sqrt[3]{\frac{29+3\sqrt{93}}{2}}}{3}\approx 1.465571231876768.$$
这个表达式等价于方程
$$x^3-x^2-1=0$$
的唯一实根，因此有
$$r^3=r^2+1.$$
把上式乘以 \(r^{e-2}\)，就得到对所有整数 \(e\) 都成立的递推关系
$$r^{e+1}=r^e+r^{e-2}.$$
这一条公式决定了贪心表示中指数之间能够出现什么样的间隔，也解释了为什么代码每次选完一项之后，下一次搜索可以直接跳过一段指数区间。
设当前对某个数 \(n\) 进行贪心分解，选中的第一项是最大的可行幂 \(r^e\le n\)。记剩余量为
$$R=n-r^e.$$
由于按贪心定义有 \(n<r^{e+1}\)，所以
$$0\le R<r^{e+1}-r^e.$$
再利用上面的递推关系，立刻得到
$$r^{e+1}-r^e=r^{e-2},$$
也就是
$$0\le R<r^{e-2}.$$
这说明下一项绝不可能是 \(r^{e-1}\) 或 \(r^{e-2}\)，因为这两项都已经大于当前剩余量。于是下一次真正可能被选中的指数至多只能是 \(e-3\)。对后续每一步重复同样的论证，就得到实现所遵循的贪心表示形状：
$$n=\sum_{t=1}^{\ell(n)} r^{e_t},\qquad e_1>e_2>\cdots,\qquad e_{t+1}\le e_t-3.$$
换句话说，被选中的幂是严格递减的，而且任意相邻两项的指数至少相差 3。这正是内层搜索先向下跳 3 位、再按需要继续下降的数学原因。
以 \(n=4\) 为例。先比较附近的几个幂：
$$r^3\approx 3.147899,\qquad r^4\approx 4.613470.$$
因为
$$r^3<4<r^4,$$
所以第一项必须选 \(r^3\)。此时剩余量约为
$$4-r^3\approx 0.852101.$$
再往下看，\(r^0=1\) 已经过大，而
$$r^{-1}\approx 0.682328$$
可以放进去，所以第二项是 \(r^{-1}\)。减掉以后还剩大约 \(0.169773\)，继续向下搜索可得第三项 \(r^{-5}\approx 0.147899\)，最后还剩下约 \(0.021874\)，对应第四项 \(r^{-10}\)。因此
$$4=r^3+r^{-1}+r^{-5}+r^{-10}.$$
用小数检查时会看到
$$3.147899+0.682328+0.147899+0.021874\approx 4.$$
这里的小数只是帮助理解贪心过程；等式本身是精确成立的，因为各项都来自满足三次方程的代数数 \(r\) 的幂。所以这一例给出
$$\ell(4)=4.$$
如果在每一次贪心判断中都直接比较高精度实数，代价会非常高，也很难保证边界稳定。实现采取的办法是先把每个需要的幂预计算成
$$r^e=a_e+\frac{b_e}{M}+\frac{c_e}{M^2}+O(M^{-3}),\qquad M=10^{17},$$
其中 \(a_e\)、\(b_e\)、\(c_e\) 都是整数。这样一来，一个幂就被压缩成三元组 \((a_e,b_e,c_e)\)，当前剩余量也同样写成三元组 \((R_1,R_2,R_3)\)。要判断某个幂是否不超过当前剩余量，只需要按字典序比较
$$\left(a_e,b_e,c_e\right),\qquad \left(R_1,R_2,R_3\right)$$
即可，不必在内层循环中继续做任意精度浮点运算。每次减法之后，再做一次借位传播，把三层数据重新归一化；这个过程和以 \(M\) 为基数的普通定点减法完全类似。
当幂表准备好以后，每个平方 \(j^2\) 都按照同样的套路处理：
先找到不超过它的最大预计算幂，然后不断减去当前剩余量能够容纳的最大更小幂，并把所用项数累计起来。这个项数就是 \(\ell(j^2)\)，最终答案就是
$$S(m)=\sum_{j=1}^{m}\ell(j^2).$$
实现先验证两个已知检查点，确保整个贪心机制没有偏差：
$$S(10)=61,\qquad S(1000)=19403.$$
只有这些值都吻合，才继续计算目标 \(m=5{,}000{,}000\) 的结果。
C++ 和 Java 实现首先用高精度十进制运算求出基数 \(r\)，然后在一个足够宽的有限指数区间内预计算所有需要的 \(r^e\)。每个幂都被拆成三层整数，从而保证真正的主循环只处理整数级别的比较、减法和借位修正。
对每个平方数，程序先定位首项幂，再把剩余量初始化成同样的三层格式，随后自上而下寻找下一个可行项，做一次三层减法并把表示长度加一。由于 \(j^2\) 随 \(j\) 单调递增，寻找首项幂的指针在整轮扫描中只会向前移动，不会反复从头开始。Python 实现则调用同一套已编译算法，因此三种语言版本共享相同的贪心分解逻辑和相同的检查点。
设 \(W=E_{\max}-E_{\min}+1\) 表示预计算指数窗口的大小。构造幂表需要 \(O(W)\) 次高精度步骤以及 \(O(W)\) 的内存。遍历全部 \(j=1,\dots,m\) 时，首项幂的向前搜索是单调的，因此这一部分总成本是 \(O(W+m)\)。真正占主导的是贪心减法过程，其成本与所有表示中被选项的总数成正比：
$$O\left(W+m+\sum_{j=1}^{m}\ell(j^2)\right).$$
在实现里，\(W\) 是固定常数，所以相对 \(m\) 而言内存开销可以看成常数级，运行时间则基本上与所有贪心表示的总输出长度线性相关。
Пусть \(r\) — иррациональное основание, используемое в задаче. Для каждого положительного целого \(n\) рассматривается его жадное представление в виде суммы различных степеней \(r\); через \(\ell(n)\) обозначим число выбранных степеней. Требуется вычислить
$$S(m)=\sum_{j=1}^{m}\ell(j^2),\qquad m=5{,}000{,}000.$$
Главная трудность в том, что основание иррационально. Значит, реализация должна выполнять миллионы сравнений и вычитаний так, чтобы ни ошибка округления, ни избыточная стоимость арифметики высокой точности не испортили жадный выбор.
Решение опирается на простую кубическую связь для основания и на устойчивое фиксированное кодирование его степеней.
Основание равно
$$r=\frac{1+\sqrt[3]{\frac{29-3\sqrt{93}}{2}}+\sqrt[3]{\frac{29+3\sqrt{93}}{2}}}{3}\approx 1.465571231876768.$$
Это единственный вещественный корень уравнения
$$x^3-x^2-1=0,$$
поэтому выполняется тождество
$$r^3=r^2+1.$$
Умножая его на \(r^{e-2}\), получаем рекуррентную формулу
$$r^{e+1}=r^e+r^{e-2}.$$
Именно она задает структуру жадного разложения.
Пусть жадный алгоритм выбрал на текущем шаге наибольшую допустимую степень \(r^e\le n\). Обозначим остаток через \(R=n-r^e\). Так как по определению \(n<r^{e+1}\), имеем
$$0\le R<r^{e+1}-r^e=r^{e-2}.$$
Следовательно, следующий член не может быть равен ни \(r^{e-1}\), ни \(r^{e-2}\); его показатель не превосходит \(e-3\). Повторяя то же рассуждение на каждом шаге, получаем жадную форму, которую используют реализации:
$$n=\sum_{t=1}^{\ell(n)} r^{e_t},\qquad e_1>e_2>\cdots,\qquad e_{t+1}\le e_t-3.$$
Поэтому после выбора очередного члена поиск следующего кандидата можно сразу начинать на три позиции ниже и только затем, если нужно, двигаться еще вниз.
Возьмем \(n=4\). Поскольку
$$r^3\approx 3.147899<4<r^4\approx 4.613470,$$
первый жадный член равен \(r^3\). Остаток примерно равен \(0.852101\), поэтому следующим допустимым членом становится \(r^{-1}\approx 0.682328\). Продолжая процесс, получаем
$$4=r^3+r^{-1}+r^{-5}+r^{-10}.$$
Численно это выглядит так:
$$3.147899+0.682328+0.147899+0.021874\approx 4.$$
Десятичные приближения здесь только поясняют выбор жадного алгоритма; само равенство точное, потому что все слагаемые являются степенями алгебраического числа \(r\). Значит, \(\ell(4)=4\).
Если сравнивать иррациональные числа напрямую внутри внутреннего цикла, решение станет и медленным, и хрупким. Поэтому каждая степень заранее записывается как
$$r^e=a_e+\frac{b_e}{M}+\frac{c_e}{M^2}+O(M^{-3}),\qquad M=10^{17},$$
где \(a_e\), \(b_e\), \(c_e\) — целые числа, полученные из высокоточного вычисления \(r^e\). Остаток хранится в том же формате. Чтобы проверить, помещается ли очередная степень в остаток, достаточно лексикографически сравнить тройки
$$\left(a_e,b_e,c_e\right),\qquad \left(R_1,R_2,R_3\right).$$
После каждого вычитания переносы и заимствования нормализуют три компоненты точно так же, как при обычной арифметике по основанию \(M\).
Для каждого квадрата \(j^2\) алгоритм находит наибольшую предварительно вычисленную степень, не превосходящую это число, затем многократно вычитает наибольшую допустимую меньшую степень и считает число использованных членов. Это и есть \(\ell(j^2)\), поэтому итоговая величина равна
$$S(m)=\sum_{j=1}^{m}\ell(j^2).$$
Перед полным запуском реализации проверяют два контрольных значения:
$$S(10)=61,\qquad S(1000)=19403.$$
Они подтверждают, что жадное разложение и фиксированное представление степеней согласованы правильно.
Реализации на C++ и Java сначала вычисляют алгебраическое основание с высокой десятичной точностью, а затем строят таблицу степеней на конечном диапазоне показателей, достаточном для целевого расчета. Каждая степень разбивается на три целочисленных слоя, чтобы внутренний жадный цикл обходился без многоточечной арифметики.
Для каждого квадрата реализация находит ведущую степень, инициализирует остаток в том же трехслойном формате, затем ищет вниз следующий допустимый член, вычитает его с обработкой заимствований и увеличивает длину представления. Поскольку квадраты растут вместе с \(j\), поиск начального показателя по таблице продвигается только вперед. Реализация на Python делегирует той же скомпилированной процедуре, поэтому все три языковые версии используют один и тот же жадный алгоритм и одни и те же контрольные значения.
Пусть \(W=E_{\max}-E_{\min}+1\) — размер предварительно вычисленного окна показателей. Построение таблицы требует \(O(W)\) высокоточных шагов и \(O(W)\) памяти. На всем диапазоне \(j=1,\dots,m\) прямой поиск ведущей степени монотонен, поэтому его общий вклад равен \(O(W+m)\). Основная стоимость определяется самим жадным вычитанием и пропорциональна общему числу выбранных членов:
$$O\left(W+m+\sum_{j=1}^{m}\ell(j^2)\right).$$
Так как \(W\) в реализациях фиксировано, расход памяти по существу постоянен относительно \(m\), а время работы практически линейно по суммарной длине всех жадных разложений.
ليكن \(r\) هو الأساس غير النسبي المستخدم في المسألة. لكل عدد صحيح موجب \(n\)، ننظر إلى تمثيله الجشع على صورة مجموع لقوى مميزة لـ \(r\)، ونرمز بعدد الحدود المختارة بالرمز \(\ell(n)\). المطلوب هو حساب
$$S(m)=\sum_{j=1}^{m}\ell(j^2),\qquad m=5{,}000{,}000.$$
الصعوبة الأساسية أن الأساس نفسه غير نسبي، لذلك يجب على التنفيذ أن يجري ملايين المقارنات وعمليات الطرح بدقة كافية حتى لا تغيّر أخطاء التقريب اختيارات الخوارزمية الجشعة.
تعتمد التطبيقات على حقيقة جبرية بسيطة تخص الأساس، وعلى طريقة مستقرة لتخزين القوى ومقارنتها داخل الحلقة الداخلية.
الأساس هو
$$r=\frac{1+\sqrt[3]{\frac{29-3\sqrt{93}}{2}}+\sqrt[3]{\frac{29+3\sqrt{93}}{2}}}{3}\approx 1.465571231876768.$$
وهذا هو الجذر الحقيقي الوحيد للمعادلة
$$x^3-x^2-1=0,$$
ومن ثم يحقق العلاقة
$$r^3=r^2+1.$$
وبضرب هذه العلاقة في \(r^{e-2}\) نحصل على
$$r^{e+1}=r^e+r^{e-2}.$$
هذه الصيغة هي التي تحدد شكل التمثيل الجشع كله.
افترض أن الخوارزمية الجشعة اختارت في خطوة ما أكبر قوة ممكنة \(r^e\le n\). إذا كان الباقي هو \(R=n-r^e\)، فبما أن \(n<r^{e+1}\) فإن
$$0\le R<r^{e+1}-r^e=r^{e-2}.$$
إذن الحد التالي لا يمكن أن يكون \(r^{e-1}\) ولا \(r^{e-2}\)، بل لا بد أن يكون أسه على الأكثر \(e-3\). بتكرار الفكرة نفسها في كل خطوة نحصل على الصورة الجشعة التي تعتمدها التطبيقات:
$$n=\sum_{t=1}^{\ell(n)} r^{e_t},\qquad e_1>e_2>\cdots,\qquad e_{t+1}\le e_t-3.$$
ولهذا يبدأ البحث عن الحد التالي مباشرة بعد النزول ثلاث مراتب في الأسس، ثم يواصل النزول فقط إذا كان ذلك المرشح الأول ما يزال أكبر من الباقي.
لنأخذ \(n=4\). بما أن
$$r^3\approx 3.147899<4<r^4\approx 4.613470,$$
فالحد الأول هو \(r^3\). يصبح الباقي تقريبًا \(0.852101\)، ولذلك يكون الحد المسموح التالي هو \(r^{-1}\approx 0.682328\). وبالاستمرار نحصل على
$$4=r^3+r^{-1}+r^{-5}+r^{-10}.$$
عدديًا،
$$3.147899+0.682328+0.147899+0.021874\approx 4.$$
هذه القيم العشرية تشرح فقط قرارات الخوارزمية الجشعة، أما المساواة نفسها فهي دقيقة تمامًا لأن جميع الحدود قوى للعدد الجبري \(r\). ولذلك فإن
$$\ell(4)=4.$$
لو قارنا الأعداد غير النسبية مباشرة داخل الحلقة الداخلية فسيصبح التنفيذ أبطأ وأقل استقرارًا. لذلك تُحسب كل قوة مسبقًا في الصورة
$$r^e=a_e+\frac{b_e}{M}+\frac{c_e}{M^2}+O(M^{-3}),\qquad M=10^{17},$$
حيث \(a_e\) و\(b_e\) و\(c_e\) أعداد صحيحة ناتجة من تقييم عالي الدقة للقوة \(r^e\). ويُخزن الباقي الحالي بالصيغة الثلاثية نفسها. وعند فحص ما إذا كانت قوة معينة لا تتجاوز الباقي، يكفي إجراء مقارنة معجمية بين الثلاثيتين
$$\left(a_e,b_e,c_e\right),\qquad \left(R_1,R_2,R_3\right).$$
بعد كل عملية طرح تُجرى معالجة للاستلاف بحيث تبقى الطبقات الثلاث ممثلة للباقي بصورة منضبطة، تمامًا كما يحدث في حساب ثابت النقطة على أساس \(M\).
لكل مربع \(j^2\)، تجد الخوارزمية أكبر قوة محسوبة مسبقًا لا تتجاوزه، ثم تطرح مرارًا أكبر قوة أصغر ما تزال ممكنة، وتعدّ عدد الحدود المستخدمة. هذا العدد هو \(\ell(j^2)\)، ومن ثم يكون الجواب النهائي
$$S(m)=\sum_{j=1}^{m}\ell(j^2).$$
وقبل الحساب الكامل تتحقق التطبيقات من نقطتي فحص معروفتين:
$$S(10)=61,\qquad S(1000)=19403.$$
هاتان القيمتان تؤكدان أن التمثيل الجشع وآلية المقارنة ثابتة النقطة يعملان معًا بصورة صحيحة.
تنفذ نسختا C++ وJava أولًا حسابًا عالي الدقة للأساس الجبري \(r\)، ثم تبنيان جدولًا للقوى على نافذة من الأسس تكفي للحساب المطلوب. بعد ذلك تُجزأ كل قوة إلى ثلاث طبقات صحيحة، حتى تبقى الحلقة الجشعة الداخلية بعيدة عن الحسابات متعددة الدقة.
بالنسبة إلى كل مربع، يحدد التنفيذ القوة القائدة، ثم يهيئ الباقي بالصيغة الثلاثية نفسها، وبعد ذلك يبحث نزولًا عن الحد التالي المسموح، ويطرحه مع معالجة الاستلاف، ثم يزيد طول التمثيل. وبما أن القيم \(j^2\) تزداد مع \(j\)، فإن البحث عن الأس الأولي يتحرك إلى الأمام فقط عبر الجدول. أما تنفيذ Python فيستدعي الخوارزمية المترجمة نفسها، ولذلك تشترك اللغات الثلاث في التمثيل الجشع نفسه وفي نقاط الفحص نفسها.
لتكن \(W=E_{\max}-E_{\min}+1\) هي سعة نافذة الأسس المحسوبة مسبقًا. بناء الجدول يكلف \(O(W)\) خطوة عالية الدقة وذاكرة \(O(W)\). وعلى امتداد المسح الكامل \(j=1,\dots,m\)، يكون البحث الأمامي عن القوة القائدة أحادي الاتجاه، وبالتالي يضيف كلفة كلية مقدارها \(O(W+m)\). أما الكلفة المسيطرة فهي كلفة الطرح الجشع نفسها، وهي متناسبة مع العدد الكلي للحدود المختارة:
$$O\left(W+m+\sum_{j=1}^{m}\ell(j^2)\right).$$
وبما أن \(W\) ثابت في التطبيقات، فإن استهلاك الذاكرة يكون عمليًا ثابتًا بالنسبة إلى \(m\)، ويصبح زمن التنفيذ قريبًا من الخطية في الطول الكلي لجميع التمثيلات الجشعة.