We seek every palindromic integer \(n<10^8\) that can be written as a sum of consecutive positive squares with at least two terms:
$$n=a^2+(a+1)^2+\cdots+b^2,\qquad 1\le a<b.$$
The final answer is the sum of those palindromic values, not the number of representations. That distinction matters because the same palindrome may arise from more than one interval of consecutive squares, so valid values must be counted only once.
The implementations do not search blindly. They convert every consecutive-square sum into a difference of square-prefix totals, use monotonic growth to stop each search branch as soon as it becomes too large, and store successful palindromes in a set so repeated representations do not change the final total.
Define the prefix sum of squares
$$P_n=\sum_{k=1}^{n} k^2=\frac{n(n+1)(2n+1)}{6}.$$
Then every block of consecutive squares from \(a\) through \(b\) can be written as
$$S(a,b)=\sum_{k=a}^{b} k^2=P_b-P_{a-1}=\frac{b(b+1)(2b+1)-(a-1)a(2a-1)}{6}.$$
This is the central algebraic object of the problem. Once the prefix totals are known, the sum for any interval \([a,b]\) is obtained in constant time from one subtraction instead of recomputing every square inside that interval.
If a consecutive-square sum is below \(10^8\), then in particular its largest term satisfies \(b^2<10^8\). Hence \(b<10^4\), so only starting and ending values up to the square-root scale of the limit ever matter.
There is also a stronger bound on the starting point. Because the interval must contain at least two terms, the smallest admissible sum beginning at \(a\) is
$$a^2+(a+1)^2=2a^2+2a+1.$$
If this already exceeds the limit, then no larger end point can rescue that start. Solving \(2a^2+2a+1<10^8\) shows that starts beyond roughly \(7070\) are mathematically impossible. The implementations use the simpler safe ceiling near \(\sqrt{10^8}\) when building the prefix table, and the later monotonic break discards the impossible tails automatically.
For a fixed start \(a\), the interval sum grows strictly as \(b\) grows:
$$S(a,b+1)=S(a,b)+(b+1)^2.$$
Because \((b+1)^2>0\), once \(S(a,b)\ge 10^8\) for some end point \(b\), every larger end point will also fail. This monotonicity is the key invariant that makes the double loop efficient: the inner scan for a fixed start can stop immediately at the first overshoot.
Take \(a=6\) and \(b=8\). Then
$$S(6,8)=6^2+7^2+8^2=36+49+64=149,$$
and \(149\) is palindromic. Using prefix sums gives the same value more systematically:
$$P_8=\frac{8\cdot 9\cdot 17}{6}=204,\qquad P_5=\frac{5\cdot 6\cdot 11}{6}=55,$$
so
$$S(6,8)=P_8-P_5=204-55=149.$$
If we extend the interval by one term, the next sum is
$$S(6,9)=149+9^2=230,$$
which illustrates the strict upward march of the right endpoint and why the break condition is correct.
The problem asks for the sum of palindromic numbers that admit such a representation, not for the sum over all representations. Therefore the mathematically correct accumulator is a set of values, not a running total inside the nested loops. Whenever a palindromic interval sum reappears from a different pair \((a,b)\), it should leave the final answer unchanged.
The C++, Python, and Java implementations first compute the least integer whose square is not below the limit and allocate a prefix array up to that point. Each entry stores the cumulative total \(1^2+2^2+\cdots+i^2\). This transforms every later interval query into a single subtraction.
The implementation then iterates over every start \(a\) and every end \(b>a\). For each pair it evaluates \(P_b-P_{a-1}\). If that value reaches the limit, the inner loop stops immediately because all larger end points would only increase the sum. Otherwise the decimal expansion is tested for the palindrome property by comparing it with its reversal.
Whenever an interval sum is palindromic, it is inserted into a set of discovered values. After the full scan, the program adds the elements of that set to produce the final answer. The three languages follow the same mathematical routine; one implementation also performs a small checkpoint on the smaller limit \(10^3\), where the correct total is \(4164\), before tackling the full \(10^8\) search.
Let \(L\) be the limit and \(B=\lceil\sqrt{L}\rceil\). Building the prefix table costs \(O(B)\) time and \(O(B)\) memory.
The nested enumeration has worst-case size \(O(B^2)\), because both endpoints live on the square-root scale. Each palindrome test inspects \(O(\log L)\) digits, so the overall worst-case running time is \(O(B^2\log L)\). For this problem \(L=10^8\) and \(B=10^4\), which is small enough for a direct search, especially because the monotone break prunes the inner loops aggressively. Memory usage is \(O(B+U)\), where \(U\) is the number of distinct palindromic sums retained in the set.
Gesucht sind alle palindromischen Zahlen \(n<10^8\), die sich als Summe aufeinanderfolgender positiver Quadrate mit mindestens zwei Summanden schreiben lassen:
$$n=a^2+(a+1)^2+\cdots+b^2,\qquad 1\le a<b.$$
Am Ende wird über diese palindromischen Werte summiert, nicht über ihre Darstellungen. Genau das macht die Eindeutigkeit wichtig: Derselbe Palindromwert kann aus mehreren Intervallen aufeinanderfolgender Quadrate entstehen und darf trotzdem nur einmal in die Endsumme eingehen.
Die Lösung arbeitet nicht mit einer naiven Summation jeder einzelnen Folge. Stattdessen werden Präfixsummen der Quadrate aufgebaut, jede Intervallsumme als Differenz zweier Präfixwerte berechnet, die Monotonie im rechten Endpunkt ausgenutzt und alle gültigen Palindrome in einer Menge gesammelt.
Definiere die Präfixsumme
$$P_n=\sum_{k=1}^{n} k^2=\frac{n(n+1)(2n+1)}{6}.$$
Dann gilt für jedes Intervall von \(a\) bis \(b\):
$$S(a,b)=\sum_{k=a}^{b} k^2=P_b-P_{a-1}=\frac{b(b+1)(2b+1)-(a-1)a(2a-1)}{6}.$$
Das ist das zentrale mathematische Objekt des Problems. Sobald die Präfixwerte vorliegen, kostet die Summe eines beliebigen Quadrateblocks nur noch eine Subtraktion statt einer vollständigen Neuberechnung.
Liegt eine solche Summe unter \(10^8\), dann gilt insbesondere \(b^2<10^8\) für den größten Summanden. Also ist \(b<10^4\), und alle relevanten Start- und Endwerte liegen auf der Größenordnung der Quadratwurzel der Schranke.
Für den Startwert gibt es sogar eine schärfere Überlegung. Da mindestens zwei Terme vorkommen müssen, ist die kleinste zulässige Summe mit Start \(a\)
$$a^2+(a+1)^2=2a^2+2a+1.$$
Wenn bereits dieser Ausdruck die Grenze überschreitet, kann kein größeres Ende mehr helfen. Aus \(2a^2+2a+1<10^8\) folgt, dass Starts oberhalb von ungefähr \(7070\) mathematisch ausscheiden. Die Implementierungen bauen dennoch bequem eine sichere Präfixtabelle bis nahe \(\sqrt{10^8}\) und verlassen sich danach auf den Monotonie-Abbruch.
Für festes \(a\) wächst die Intervallsumme streng mit \(b\):
$$S(a,b+1)=S(a,b)+(b+1)^2.$$
Weil \((b+1)^2>0\) ist, gilt: Sobald \(S(a,b)\ge 10^8\) erreicht ist, werden alle späteren Werte ebenfalls zu groß sein. Genau diese Invariante macht die verschachtelte Suche effizient, denn die innere Schleife darf beim ersten Überschreiten sofort abbrechen.
Nehmen wir \(a=6\) und \(b=8\). Dann ist
$$S(6,8)=6^2+7^2+8^2=36+49+64=149,$$
und \(149\) ist palindromisch. Mit Präfixsummen erhält man denselben Wert systematisch:
$$P_8=\frac{8\cdot 9\cdot 17}{6}=204,\qquad P_5=\frac{5\cdot 6\cdot 11}{6}=55,$$
also
$$S(6,8)=P_8-P_5=204-55=149.$$
Erweitert man das Intervall um einen weiteren Summanden, so folgt
$$S(6,9)=149+9^2=230.$$
Damit sieht man direkt, wie der rechte Endpunkt die Summe streng nach oben treibt und warum die Abbruchbedingung korrekt ist.
Gesucht ist die Summe der palindromischen Zahlen, die eine zulässige Darstellung besitzen, nicht die Summe über alle Darstellungen. Deshalb ist der mathematisch richtige Sammelbehälter eine Menge von Werten und kein laufender Gesamtzähler innerhalb der Doppelschleife. Taucht derselbe Palindromwert über ein anderes Intervall erneut auf, darf sich das Endergebnis nicht mehr ändern.
Die C++-, Python- und Java-Implementierungen bestimmen zunächst die kleinste ganze Zahl, deren Quadrat die Schranke erreicht oder überschreitet, und legen bis dorthin ein Präfixarray an. Jeder Eintrag speichert die kumulierte Summe \(1^2+2^2+\cdots+i^2\). Dadurch wird jede spätere Intervallabfrage auf eine einzige Differenz reduziert.
Anschließend iteriert die Implementierung über jeden Start \(a\) und jedes Ende \(b>a\). Für jedes Paar wird \(P_b-P_{a-1}\) gebildet. Erreicht diese Summe die Schranke, bricht die innere Schleife sofort ab, weil alle größeren Enden nur noch größere Summen liefern würden. Andernfalls wird die Dezimaldarstellung auf Palindromeigenschaft geprüft, indem sie mit ihrer Umkehrung verglichen wird.
Ist eine Intervallsumme palindromisch, wird sie in eine Menge eingefügt. Nach dem vollständigen Suchlauf werden die Elemente dieser Menge summiert. Alle drei Sprachen folgen demselben mathematischen Schema; eine Implementierung prüft zusätzlich vorab den kleineren Kontrollfall \(10^3\), bei dem die korrekte Summe \(4164\) ist.
Sei \(L\) die Schranke und \(B=\lceil\sqrt{L}\rceil\). Der Aufbau der Präfixtabelle benötigt \(O(B)\) Zeit und \(O(B)\) Speicher.
Die verschachtelte Enumeration hat im Worst Case Größe \(O(B^2)\), weil beide Intervallgrenzen auf Quadratwurzel-Skala liegen. Jeder Palindromtest betrachtet \(O(\log L)\) Ziffern, also beträgt die gesamte Worst-Case-Laufzeit \(O(B^2\log L)\). Für dieses Problem ist \(L=10^8\) und damit \(B=10^4\); das ist gut beherrschbar, zumal der monotone Abbruch viele innere Schleifen früh beendet. Der Speicherbedarf ist \(O(B+U)\), wobei \(U\) die Anzahl der verschiedenen palindromischen Summen in der Menge bezeichnet.
Aranan şey, \(10^8\)'den küçük olup en az iki terimli ardışık pozitif kareler toplamı şeklinde yazılabilen tüm palindromik tamsayılardır:
$$n=a^2+(a+1)^2+\cdots+b^2,\qquad 1\le a<b.$$
Sonuç, bu palindromik değerlerin toplamıdır; gösterimlerin sayısı değildir. Bu ayrım önemlidir, çünkü aynı palindrom sayı farklı \((a,b)\) aralıklarından gelebilir ve buna rağmen son toplamda yalnızca bir kez yer almalıdır.
Çözüm, her aralığın karesini tek tek yeniden toplamaz. Bunun yerine karelerin ön ek toplamlarını kurar, her ardışık kareler toplamını iki ön ek toplamın farkına çevirir, sağ uçtaki tekdüze büyümeyi kullanarak gereksiz taramayı erken durdurur ve bulunan palindromları bir kümede tutarak tekrar sayımı engeller.
Önce
$$P_n=\sum_{k=1}^{n} k^2=\frac{n(n+1)(2n+1)}{6}$$
ön ek toplamını tanımlayalım. O zaman \(a\) ile \(b\) arasındaki ardışık karelerin toplamı
$$S(a,b)=\sum_{k=a}^{b} k^2=P_b-P_{a-1}=\frac{b(b+1)(2b+1)-(a-1)a(2a-1)}{6}$$
olur. Problemin temel matematiksel nesnesi budur. Ön ek toplamlar hazırlandığında herhangi bir \([a,b]\) aralığının değeri sabit zamanda, yalnızca bir çıkarma ile bulunur.
Bir ardışık kareler toplamı \(10^8\)'den küçükse, en büyük terimi de zorunlu olarak \(b^2<10^8\) sağlar. Dolayısıyla \(b<10^4\) olur; yani anlamlı başlangıç ve bitiş noktalarının tümü limitin karekökü ölçeğindedir.
Başlangıç noktası için daha keskin bir sınır da vardır. En az iki terim gerektiğinden, \(a\) ile başlayan en küçük uygun toplam
$$a^2+(a+1)^2=2a^2+2a+1$$
şeklindedir. Bu ifade bile sınırı aşıyorsa, daha büyük hiçbir bitiş değeri o başlangıcı geçerli hâle getiremez. \(2a^2+2a+1<10^8\) eşitsizliği yaklaşık \(7070\)'ten büyük başlangıçların matematiksel olarak işe yaramadığını gösterir. Uygulamalar ise daha basit ve güvenli olan \(\sqrt{10^8}\) civarına kadar ön ek tablosu kurar; sonrasında tekdüze büyüme zaten boş bölgeleri otomatik olarak eler.
Sabit bir \(a\) için aralık toplamı \(b\) arttıkça kesin olarak büyür:
$$S(a,b+1)=S(a,b)+(b+1)^2.$$
\((b+1)^2>0\) olduğu için, bir kez \(S(a,b)\ge 10^8\) olduğunda daha büyük tüm \(b\) değerleri de başarısız olacaktır. Çift döngünün pratikte hızlı çalışmasının temel değişmezi budur: her başlangıç için iç döngü, ilk taşma anında güvenle durdurulabilir.
\(a=6\) ve \(b=8\) seçelim. O zaman
$$S(6,8)=6^2+7^2+8^2=36+49+64=149,$$
ve \(149\) bir palindromdur. Aynı hesap ön ek toplamlarıyla da yapılır:
$$P_8=\frac{8\cdot 9\cdot 17}{6}=204,\qquad P_5=\frac{5\cdot 6\cdot 11}{6}=55,$$
dolayısıyla
$$S(6,8)=P_8-P_5=204-55=149.$$
Aralığı bir terim daha uzatırsak
$$S(6,9)=149+9^2=230$$
elde edilir. Bu da sağ uç büyüdükçe toplamın nasıl kesin biçimde arttığını açıkça gösterir.
Sorulan nicelik, böyle bir gösterime sahip palindrom sayıların toplamıdır; gösterimlerin toplamı değildir. Bu nedenle doğru matematiksel biriktirme yapısı, iç döngü içinde hemen eklenen bir toplam değil, değerleri tekilleştiren bir kümedir. Aynı palindrom başka bir \((a,b)\) aralığından yeniden çıkarsa sonuç değişmemelidir.
C++, Python ve Java uygulamaları önce karesi limite eşit ya da ondan büyük olan en küçük tamsayıyı bulur ve o noktaya kadar bir ön ek dizisi oluşturur. Her hücre \(1^2+2^2+\cdots+i^2\) toplamını saklar. Böylece sonraki her aralık sorgusu tek bir çıkarma işlemine dönüşür.
Daha sonra uygulama her başlangıç \(a\) ve her \(b>a\) bitişi üzerinden geçer. Her çift için \(P_b-P_{a-1}\) hesaplanır. Bu değer limite ulaşır ulaşmaz iç döngü kırılır, çünkü daha büyük bitişler sadece daha büyük toplamlar üretir. Aksi durumda ondalık yazım ters çevrilmiş hâliyle karşılaştırılarak palindrom testi yapılır.
Bir aralık toplamı palindrom ise keşfedilen değerler kümesine eklenir. Taramanın sonunda bu kümenin elemanları toplanır. Üç dildeki uygulama aynı matematiksel akışı izler; bunlardan biri ayrıca tam aramaya başlamadan önce \(10^3\) sınırı için doğru toplamın \(4164\) olduğunu kontrol eden küçük bir doğrulama da yapar.
\(L\) limit ve \(B=\lceil\sqrt{L}\rceil\) olsun. Ön ek tablosunu kurmak \(O(B)\) zaman ve \(O(B)\) bellek gerektirir.
İç içe taramanın en kötü durum büyüklüğü \(O(B^2)\)'dir; çünkü hem başlangıç hem bitiş değerleri karekök ölçeğinde kalır. Her palindrom kontrolü \(O(\log L)\) basamak inceler, dolayısıyla toplam en kötü durum çalışma süresi \(O(B^2\log L)\) olur. Bu problemde \(L=10^8\) ve \(B=10^4\) olduğundan yöntem doğrudan uygulanabilir; ayrıca taşma anındaki erken durdurma, pratikte pek çok iç döngüyü kısa keser. Bellek kullanımı \(O(B+U)\)'dur; burada \(U\) kümede tutulan farklı palindrom toplamların sayısıdır.
Se buscan todos los enteros palindrómicos \(n<10^8\) que pueden escribirse como suma de cuadrados positivos consecutivos con al menos dos términos:
$$n=a^2+(a+1)^2+\cdots+b^2,\qquad 1\le a<b.$$
La respuesta final es la suma de esos valores palindrómicos, no la suma de sus representaciones. Esa diferencia es esencial, porque el mismo palíndromo puede aparecer a partir de más de un intervalo de cuadrados consecutivos y, aun así, debe contarse una sola vez.
La solución no recalcula cada bloque de cuadrados desde cero. En su lugar, construye sumas prefijo de cuadrados, expresa cada suma consecutiva como la diferencia entre dos prefijos, usa el crecimiento monótono del extremo derecho para cortar la búsqueda en cuanto se supera el límite y almacena los palíndromos encontrados en un conjunto para eliminar duplicados.
Definimos
$$P_n=\sum_{k=1}^{n} k^2=\frac{n(n+1)(2n+1)}{6}.$$
Entonces cualquier bloque de cuadrados consecutivos desde \(a\) hasta \(b\) satisface
$$S(a,b)=\sum_{k=a}^{b} k^2=P_b-P_{a-1}=\frac{b(b+1)(2b+1)-(a-1)a(2a-1)}{6}.$$
Ese es el objeto algebraico central del problema. Una vez conocidos los valores prefijo, la suma del intervalo \([a,b]\) se obtiene en tiempo constante con una sola resta.
Si una suma de cuadrados consecutivos está por debajo de \(10^8\), entonces su término más grande también cumple \(b^2<10^8\). Por tanto \(b<10^4\), y tanto los inicios como los finales relevantes viven en la escala de \(\sqrt{10^8}\).
Para el inicio existe además una cota más fuerte. Como debe haber al menos dos términos, la suma mínima que empieza en \(a\) es
$$a^2+(a+1)^2=2a^2+2a+1.$$
Si esa cantidad ya supera el límite, ningún extremo derecho mayor puede hacer válido ese inicio. Resolver \(2a^2+2a+1<10^8\) muestra que los inicios por encima de aproximadamente \(7070\) son imposibles desde el punto de vista matemático. Las implementaciones, sin embargo, usan la cota segura y sencilla cercana a \(\sqrt{10^8}\) para construir la tabla de prefijos, y luego el corte monótono elimina de forma automática la cola inútil.
Para un inicio fijo \(a\), la suma crece estrictamente al aumentar \(b\):
$$S(a,b+1)=S(a,b)+(b+1)^2.$$
Como \((b+1)^2>0\), una vez que \(S(a,b)\ge 10^8\), todos los extremos derechos posteriores también fallarán. Esta monotonía es la invariante que permite la ruptura temprana del bucle interior.
Tomemos \(a=6\) y \(b=8\). Entonces
$$S(6,8)=6^2+7^2+8^2=36+49+64=149,$$
y \(149\) es palindrómico. Con sumas prefijo se obtiene el mismo resultado de forma sistemática:
$$P_8=\frac{8\cdot 9\cdot 17}{6}=204,\qquad P_5=\frac{5\cdot 6\cdot 11}{6}=55,$$
de modo que
$$S(6,8)=P_8-P_5=204-55=149.$$
Si ampliamos el intervalo en un término más, obtenemos
$$S(6,9)=149+9^2=230,$$
lo que ilustra con claridad que el extremo derecho solo puede hacer crecer la suma.
La cantidad pedida es la suma de los números palindrómicos que admiten alguna representación válida, no la suma sobre todas las representaciones posibles. Por eso el acumulador correcto es un conjunto de valores. Si el mismo palíndromo aparece otra vez desde un intervalo distinto \((a,b)\), el resultado final no debe cambiar.
Las implementaciones en C++, Python y Java calculan primero el menor entero cuyo cuadrado ya no es menor que el límite y reservan un arreglo de prefijos hasta ese punto. Cada entrada guarda la suma acumulada \(1^2+2^2+\cdots+i^2\). Así, cualquier suma de intervalo posterior se reduce a una sola resta.
Después, la implementación recorre cada inicio \(a\) y cada final \(b>a\). Para cada pareja evalúa \(P_b-P_{a-1}\). Si ese valor alcanza el límite, el bucle interior se detiene de inmediato porque todos los finales mayores producirán sumas aún mayores. En caso contrario, se comprueba si la representación decimal es palindrómica comparándola con su inversión.
Cuando una suma de intervalo es palindrómica, se inserta en un conjunto de valores encontrados. Tras completar el barrido, se suman los elementos de ese conjunto. Los tres lenguajes implementan el mismo procedimiento matemático; una de las versiones añade además una verificación pequeña con el límite \(10^3\), cuyo total correcto es \(4164\), antes de ejecutar la búsqueda completa.
Sea \(L\) el límite y \(B=\lceil\sqrt{L}\rceil\). Construir la tabla de prefijos cuesta \(O(B)\) tiempo y \(O(B)\) memoria.
La enumeración doble tiene tamaño peor caso \(O(B^2)\), porque ambos extremos del intervalo viven en la escala de la raíz cuadrada. Cada prueba de palíndromo examina \(O(\log L)\) dígitos, así que el tiempo total en peor caso es \(O(B^2\log L)\). En este problema \(L=10^8\) y \(B=10^4\), un tamaño perfectamente manejable, más aún porque la ruptura temprana por monotonía recorta muchas iteraciones reales. El uso de memoria es \(O(B+U)\), donde \(U\) es el número de sumas palindrómicas distintas almacenadas en el conjunto.
目标是找出所有小于 \(10^8\) 的回文整数 \(n\)，并且这些数能够表示成至少两个连续正平方数之和：
$$n=a^2+(a+1)^2+\cdots+b^2,\qquad 1\le a<b.$$
最后要求的是这些回文值本身的总和，而不是表示方法的总数。这个区别非常关键，因为同一个回文数可能对应多个不同的连续平方区间，但在最终答案里只能计算一次。
实现并不是对每个区间重新逐项求和。它先建立平方前缀和，把任意连续平方和改写成两个前缀值的差，再利用右端点增长时总和严格增大的性质做提前终止，最后用集合保存已经找到的回文值，从而避免重复计数。
定义前缀和
$$P_n=\sum_{k=1}^{n} k^2=\frac{n(n+1)(2n+1)}{6}.$$
那么从 \(a\) 到 \(b\) 的连续平方和可以写成
$$S(a,b)=\sum_{k=a}^{b} k^2=P_b-P_{a-1}=\frac{b(b+1)(2b+1)-(a-1)a(2a-1)}{6}.$$
这就是本题最核心的数学对象。当前缀值已经准备好之后，任何区间 \([a,b]\) 的值都可以通过一次减法在常数时间内得到，而不必重新把区间里的平方数全部累加一遍。
如果某个连续平方和小于 \(10^8\)，那么它的最大项一定满足 \(b^2<10^8\)。因此 \(b<10^4\)，也就是说有意义的起点和终点都落在极限值平方根这一数量级上。
起点还可以得到更强的约束。因为题目要求至少两个平方项，所以从 \(a\) 开始的最小合法和是
$$a^2+(a+1)^2=2a^2+2a+1.$$
如果这个最小值都已经达到或超过上界，那么再把右端点向后扩展只会更大，不可能重新变成合法区间。解不等式 \(2a^2+2a+1<10^8\) 可以看出，大约从 \(7070\) 以上开始的起点在数学上已经没有希望。实现里采用了更直接也更安全的做法：前缀表建到接近 \(\sqrt{10^8}\) 的位置，然后依靠后面的单调性剪枝自然淘汰那些无效起点。
当起点 \(a\) 固定时，随着 \(b\) 增大，区间和严格递增：
$$S(a,b+1)=S(a,b)+(b+1)^2.$$
由于 \((b+1)^2>0\)，一旦某个 \(b\) 使得 \(S(a,b)\ge 10^8\)，那么所有更大的右端点都会失败。这就是代码中提前退出内层循环的关键不变量。
取 \(a=6\)、\(b=8\)。那么
$$S(6,8)=6^2+7^2+8^2=36+49+64=149,$$
而 \(149\) 正好是回文数。用前缀和同样可以得到它：
$$P_8=\frac{8\cdot 9\cdot 17}{6}=204,\qquad P_5=\frac{5\cdot 6\cdot 11}{6}=55,$$
于是
$$S(6,8)=P_8-P_5=204-55=149.$$
如果再把区间向右扩一项，就有
$$S(6,9)=149+9^2=230.$$
这个例子同时说明了两件事：前缀差分确实给出正确的区间和，而右端点增加只会让总和继续上升。
题目要求的是“满足条件的回文数之和”，不是“所有满足条件的表示式之和”。因此正确的累积方式不是在双重循环里直接把每次遇到的回文和都加进去，而是先把回文值放进集合里。若同一个回文数由另一个区间 \((a,b)\) 再次产生，最终答案不应发生变化。
C++、Python 和 Java 实现首先求出满足平方达到或超过上界的最小整数，然后建立一个到该位置为止的前缀数组。数组第 \(i\) 项保存 \(1^2+2^2+\cdots+i^2\) 的累计结果。这样后续任意区间查询都只需要做一次减法。
接着，程序枚举每个起点 \(a\) 以及每个满足 \(b>a\) 的终点。对每一对端点，先计算 \(P_b-P_{a-1}\)。如果这个值已经达到上界，就立刻停止当前起点对应的内层循环，因为更大的终点只会得到更大的和。若仍在范围内，再把该数的十进制表示与其反转结果比较，判断是否为回文。
一旦某个区间和是回文数，就把它插入集合。全部枚举结束后，再把集合中的元素求和，得到最终结果。三种语言实现遵循的数学流程完全一致；其中一个实现还会先用较小上界 \(10^3\) 做一次校验，此时正确总和为 \(4164\)，然后才运行完整的 \(10^8\) 搜索。
设上界为 \(L\)，并记 \(B=\lceil\sqrt{L}\rceil\)。构建前缀表需要 \(O(B)\) 时间和 \(O(B)\) 空间。
双重枚举在最坏情况下是 \(O(B^2)\)，因为起点和终点都处在平方根量级。每次回文检测需要查看 \(O(\log L)\) 个十进制数字，因此总的最坏时间复杂度是 \(O(B^2\log L)\)。在本题里 \(L=10^8\)、\(B=10^4\)，这个规模完全可以直接处理，而且单调性带来的提前退出会显著减少实际运行次数。空间复杂度为 \(O(B+U)\)，其中 \(U\) 是集合中保留的不重复回文和的数量。
Нужно найти все палиндромные целые числа \(n<10^8\), которые представимы в виде суммы последовательных квадратов положительных чисел, причём слагаемых должно быть как минимум два:
$$n=a^2+(a+1)^2+\cdots+b^2,\qquad 1\le a<b.$$
Искомая величина представляет собой сумму самих палиндромных значений, а не сумму всех их представлений. Это важно, потому что одно и то же палиндромное число может возникать из нескольких разных интервалов последовательных квадратов, но в окончательный ответ оно должно входить только один раз.
Решение не пересчитывает каждую последовательность квадратов заново. Вместо этого строятся префиксные суммы квадратов, любая сумма на интервале выражается как разность двух префиксов, рост по правой границе используется для ранней остановки, а найденные палиндромы складываются в множество, чтобы исключить повторный учёт.
Введём
$$P_n=\sum_{k=1}^{n} k^2=\frac{n(n+1)(2n+1)}{6}.$$
Тогда для любого интервала от \(a\) до \(b\) имеем
$$S(a,b)=\sum_{k=a}^{b} k^2=P_b-P_{a-1}=\frac{b(b+1)(2b+1)-(a-1)a(2a-1)}{6}.$$
Это главный алгебраический объект задачи. Как только массив префиксных сумм построен, значение любого интервала \([a,b]\) находится за константное время одной разностью.
Если сумма последовательных квадратов меньше \(10^8\), то её наибольший член тоже обязан удовлетворять \(b^2<10^8\). Следовательно, \(b<10^4\), и все существенные начала и концы лежат на масштабе квадратного корня от ограничения.
Для стартовой точки есть и более сильная оценка. Поскольку требуется минимум два слагаемых, наименьшая допустимая сумма, начинающаяся с \(a\), равна
$$a^2+(a+1)^2=2a^2+2a+1.$$
Если уже эта величина достигает предела, то никакое большее правое окончание ситуацию не исправит. Из неравенства \(2a^2+2a+1<10^8\) следует, что старты выше примерно \(7070\) математически бесполезны. Реализации используют более простую и безопасную верхнюю границу порядка \(\sqrt{10^8}\) при построении префиксной таблицы, а затем монотонный обрыв автоматически отсеивает пустой хвост.
При фиксированном \(a\) сумма на интервале строго возрастает с ростом \(b\):
$$S(a,b+1)=S(a,b)+(b+1)^2.$$
Так как \((b+1)^2>0\), после первого момента, когда \(S(a,b)\ge 10^8\), все большие правые границы тоже будут недопустимы. Именно эта инвариантность обеспечивает эффективность внутреннего цикла: его можно немедленно прервать при первом превышении.
Возьмём \(a=6\) и \(b=8\). Тогда
$$S(6,8)=6^2+7^2+8^2=36+49+64=149,$$
а число \(149\) является палиндромом. Через префиксные суммы получаем то же самое:
$$P_8=\frac{8\cdot 9\cdot 17}{6}=204,\qquad P_5=\frac{5\cdot 6\cdot 11}{6}=55,$$
следовательно,
$$S(6,8)=P_8-P_5=204-55=149.$$
Если расширить интервал ещё на один член, получится
$$S(6,9)=149+9^2=230.$$
Этот пример одновременно показывает и правильность формулы через префиксы, и строгий рост суммы при движении правой границы вправо.
Требуется сумма палиндромных чисел, которые имеют хотя бы одно допустимое представление, а не сумма по всем представлениям. Поэтому математически правильный накопитель здесь не текущая переменная суммы внутри двойного цикла, а множество значений. Если тот же палиндром встретится снова для другого интервала \((a,b)\), конечный результат меняться не должен.
Реализации на C++, Python и Java сначала находят наименьшее целое число, квадрат которого уже не меньше предела, и строят до этой точки массив префиксных сумм. В ячейке с индексом \(i\) хранится накопленное значение \(1^2+2^2+\cdots+i^2\). После этого любой запрос на сумму по интервалу сводится к одной разности.
Затем программа перебирает каждый старт \(a\) и каждый конец \(b>a\). Для каждой пары вычисляется \(P_b-P_{a-1}\). Если сумма достигает ограничения, внутренний цикл сразу прекращается, потому что дальнейшие значения \(b\) дадут только большие суммы. Иначе десятичная запись сравнивается со своей обратной записью, чтобы проверить палиндромность.
Каждая палиндромная сумма интервала помещается во множество найденных значений. После завершения перебора элементы этого множества суммируются. Во всех трёх языках используется одна и та же математическая схема; одна из реализаций дополнительно проверяет малый контрольный случай \(10^3\), для которого правильная сумма равна \(4164\), прежде чем переходить к полному пределу \(10^8\).
Пусть \(L\) обозначает ограничение, а \(B=\lceil\sqrt{L}\rceil\). Построение префиксной таблицы требует \(O(B)\) времени и \(O(B)\) памяти.
Двойной перебор имеет размер \(O(B^2)\) в худшем случае, поскольку обе границы интервала находятся на масштабе квадратного корня. Каждая проверка на палиндром рассматривает \(O(\log L)\) цифр, поэтому общая трудоёмкость в худшем случае равна \(O(B^2\log L)\). Для данной задачи \(L=10^8\) и \(B=10^4\), что вполне практично; кроме того, ранний останов по монотонности заметно уменьшает фактическое число проверок. Память составляет \(O(B+U)\), где \(U\) — число различных палиндромных сумм, оставшихся во множестве.
المطلوب هو إيجاد جميع الأعداد الصحيحة المتناظرة \(n<10^8\) التي يمكن كتابتها على صورة مجموع مربعات موجبة متتالية تحتوي على حدين على الأقل:
$$n=a^2+(a+1)^2+\cdots+b^2,\qquad 1\le a<b.$$
الإجابة النهائية هي مجموع هذه القيم المتناظرة نفسها، وليست مجموع عدد الطرق التي تظهر بها. هذه النقطة مهمة لأن العدد المتناظر نفسه قد ينتج من أكثر من فترة متتالية من المربعات، ومع ذلك يجب احتسابه مرة واحدة فقط.
الحل لا يعيد جمع كل فترة من الصفر. بدلاً من ذلك يبني مجاميع بادئة للمربعات، ويحوّل أي مجموع متتالٍ إلى فرق بين قيمتين بادئتين، ويستفيد من ازدياد المجموع بشكل رتيب عند تحريك الحد الأيمن، ثم يحفظ القيم المتناظرة في مجموعة حتى لا تؤثر التمثيلات المكررة في الناتج النهائي.
لنعرّف
$$P_n=\sum_{k=1}^{n} k^2=\frac{n(n+1)(2n+1)}{6}.$$
عندئذٍ يصبح مجموع المربعات المتتالية من \(a\) إلى \(b\)
$$S(a,b)=\sum_{k=a}^{b} k^2=P_b-P_{a-1}=\frac{b(b+1)(2b+1)-(a-1)a(2a-1)}{6}.$$
هذا هو الجسم الرياضي المركزي في المسألة. فبمجرد تجهيز المجاميع البادئة، يمكن حساب قيمة أي فترة \([a,b]\) في زمن ثابت بعملية طرح واحدة فقط.
إذا كان مجموع مربعات متتالية أصغر من \(10^8\)، فإن أكبر حد فيه يحقق بالضرورة \(b^2<10^8\). لذلك نحصل على \(b<10^4\)، أي إن جميع قيم البداية والنهاية المهمة تقع على مقياس الجذر التربيعي للحد الأعلى.
ويمكن أيضاً الحصول على قيد أقوى على نقطة البداية. بما أن الفترة يجب أن تحتوي على حدين على الأقل، فإن أصغر مجموع ممكن يبدأ عند \(a\) هو
$$a^2+(a+1)^2=2a^2+2a+1.$$
إذا كان هذا المقدار نفسه قد بلغ الحد أو تجاوزه، فلن يتمكن أي حد أيمن أكبر من جعل البداية صالحة. ومن حل المتباينة \(2a^2+2a+1<10^8\) نرى أن البدايات التي تتجاوز تقريباً \(7070\) مستبعدة رياضياً. أما التنفيذ فيستخدم حداً آمناً وبسيطاً قريباً من \(\sqrt{10^8}\) لبناء جدول المجاميع البادئة، ثم يترك لخاصية الرتابة مهمة التخلص من الذيل غير المفيد.
عند تثبيت \(a\)، فإن المجموع يزداد زيادة صارمة مع ازدياد \(b\):
$$S(a,b+1)=S(a,b)+(b+1)^2.$$
وبما أن \((b+1)^2>0\)، فبمجرد أن يصبح \(S(a,b)\ge 10^8\)، فإن كل القيم الأكبر لـ \(b\) ستفشل أيضاً. هذا هو الثابت الأساسي الذي يجعل الحلقة الداخلية فعالة: يمكن إيقافها فور أول تجاوز.
لنأخذ \(a=6\) و\(b=8\). عندئذٍ
$$S(6,8)=6^2+7^2+8^2=36+49+64=149,$$
والعدد \(149\) متناظر. ويمكن الوصول إلى القيمة نفسها باستخدام المجاميع البادئة:
$$P_8=\frac{8\cdot 9\cdot 17}{6}=204,\qquad P_5=\frac{5\cdot 6\cdot 11}{6}=55,$$
ومن ثم
$$S(6,8)=P_8-P_5=204-55=149.$$
وإذا مددنا الفترة بحد واحد إضافي نحصل على
$$S(6,9)=149+9^2=230.$$
هذا المثال يوضح في الوقت نفسه صحة صيغة الفروق البادئة، ويبين أن تحريك الحد الأيمن لا يمكنه إلا أن يزيد المجموع.
المطلوب هو مجموع الأعداد المتناظرة التي تمتلك تمثيلاً صالحاً واحداً على الأقل، وليس مجموع جميع التمثيلات الممكنة. لذلك فإن البنية الصحيحة للتجميع هي مجموعة للقيم، لا مجموع جارٍ داخل الحلقتين. فإذا ظهر العدد المتناظر نفسه من فترة أخرى \((a,b)\)، فلا ينبغي أن يتغير الناتج النهائي.
تبدأ تطبيقات C++ وPython وJava بحساب أصغر عدد صحيح يكون مربعه مساوياً للحد أو أكبر منه، ثم تنشئ مصفوفة بادئة حتى تلك النقطة. كل خانة تخزن المجموع التراكمي \(1^2+2^2+\cdots+i^2\). وهكذا تتحول أي عملية حساب لاحقة لمجموع فترة إلى عملية طرح واحدة.
بعد ذلك يمر التنفيذ على كل بداية \(a\) وكل نهاية \(b>a\). ولكل زوج يحسب \(P_b-P_{a-1}\). فإذا وصل هذا المجموع إلى الحد الأقصى تتوقف الحلقة الداخلية مباشرة، لأن كل النهايات الأكبر ستنتج مجاميع أكبر. وإذا بقي المجموع دون الحد، تُفحص كتابته العشرية بمقارنتها مع صورتها المعكوسة للتأكد من خاصية التناظر.
عندما تكون قيمة الفترة متناظرة، تُدرج في مجموعة القيم المكتشفة. وبعد انتهاء المسح الكامل تُجمع عناصر هذه المجموعة. اللغات الثلاث تتبع الروتين الرياضي نفسه؛ كما أن إحدى النسخ تضيف فحصاً صغيراً عند الحد \(10^3\)، حيث يكون المجموع الصحيح \(4164\)، قبل الانتقال إلى البحث الكامل تحت \(10^8\).
ليكن \(L\) هو الحد الأعلى و\(B=\lceil\sqrt{L}\rceil\). بناء جدول المجاميع البادئة يكلف \(O(B)\) زمناً و\(O(B)\) ذاكرة.
أما التعداد المزدوج فحجمه في أسوأ الأحوال هو \(O(B^2)\)، لأن حدّي الفترة كليهما يقعان على مقياس الجذر التربيعي. وكل اختبار للتناظر يفحص \(O(\log L)\) من الأرقام العشرية، لذلك تكون كلفة الزمن الكلية في أسوأ الأحوال \(O(B^2\log L)\). في هذه المسألة لدينا \(L=10^8\) و\(B=10^4\)، وهو حجم عملي تماماً، خصوصاً أن التوقف المبكر الناتج من الرتابة يقلل كثيراً من عدد المحاولات الفعلي. أما الذاكرة فهي \(O(B+U)\)، حيث \(U\) هو عدد المجاميع المتناظرة المختلفة المحفوظة في المجموعة.