A positive integer \(n\) is called an S-number if \(n\) is a perfect square and the decimal digits of \(n\) can be cut into at least two contiguous blocks whose integer values add up to \(\sqrt{n}\). The problem asks for
$$T(L)=\sum_{\substack{n\le L\\ n\text{ is an S-number}}} n.$$
Since every contributing term is a square, it is more convenient to search over roots \(r\) and test whether the decimal expansion of \(r^2\) admits such a partition.
If \(\mathcal{S}\) denotes the set of valid roots, then equivalently
$$T(L)=\sum_{\substack{1\le r\le \lfloor\sqrt{L}\rfloor\\ r\in\mathcal{S}}} r^2.$$
The implementation combines a necessary congruence filter with a depth-first search over decimal cut positions. The search is made efficient by strong lower and upper bounds for every unfinished suffix.
Let \(r\) be a candidate root and let \(n=r^2\). Write the decimal expansion of \(n\) and split it into contiguous blocks with values \(b_1,b_2,\dots,b_k\), where \(k\ge2\). Then \(r\) is valid exactly when
$$b_1+b_2+\cdots+b_k=r.$$
No operators are inserted and no digits are rearranged; only cut positions are chosen. If \(n\) has \(d\) digits, then each gap between adjacent digits is either cut or not cut, so the raw search space contains \(2^{d-1}-1\) nontrivial partitions.
Any successful split must satisfy a strong congruence. Every power of ten obeys \(10^m\equiv1\pmod 9\), so cutting a decimal string into blocks does not change its value modulo \(9\). Therefore the sum of the blocks is congruent to the original square:
$$r\equiv r^2\pmod 9.$$
This simplifies to
$$r(r-1)\equiv0\pmod 9,$$
which forces
$$r\bmod 9\in\{0,1\}.$$
This test is only necessary, not sufficient, but it removes \(7/9\) of all roots before the search starts.
Suppose some initial blocks have already been chosen and their sum is \(s\). Choose one more block, so the new partial sum becomes \(s'\). Let the remaining suffix be \(R\). Define \(D(R)\) as the sum of the digits of \(R\), and \(V(R)\) as the integer represented by the whole suffix.
Any continuation of the partition must then finish inside the interval
$$[\,s'+D(R),\,s'+V(R)\,].$$
The lower bound comes from cutting between every remaining digit. The upper bound comes from making no further cut and taking the entire suffix as one block. Therefore a branch can be discarded immediately whenever
$$s'+D(R)\gt r$$
or
$$s'+V(R)\lt r.$$
After a candidate block is chosen, the same reasoning is applied to the rest of the digits. If the running sum already exceeds \(r\), the branch stops because all block values are nonnegative. When the end of the digit string is reached, the split succeeds exactly if the accumulated sum equals \(r\).
The one-block partition \(r^2\) itself must be excluded, because the definition requires at least two parts. The implementations enforce this by ensuring that the first block ends before the last digit, so at least one cut is guaranteed.
Take \(r=45\), so \(n=r^2=2025\). The modular filter passes because \(45\equiv0\pmod 9\).
If the first block is \(2\), the remaining suffix is \(025\). Then
$$2+(0+2+5)=9,\qquad 2+25=27.$$
So every completion lies between \(9\) and \(27\), which can never reach \(45\). That entire branch is pruned immediately.
If the first block is \(20\), the suffix is \(25\). Now the feasible interval becomes
$$[27,45].$$
The target lies inside the interval, and choosing the last block as \(25\) gives
$$20+25=45.$$
Hence \(2025\) is an S-number and contributes \(2025\) to \(T(L)\).
The C++, Python, and Java implementations all follow the same structure. They iterate candidate roots \(r\) from \(2\) upward, stop once \(r^2\) exceeds the limit, and reject any root whose residue modulo \(9\) is neither \(0\) nor \(1\).
For each surviving root, the square \(r^2\) is converted to a digit sequence. Two suffix tables are prepared: one stores the value of every remaining suffix as a whole number, and the other stores the sum of the digits in that suffix. These tables let the search evaluate the interval test in constant time at every recursive node.
The search then tries each possible next block, updates the partial sum, applies the lower and upper bound checks, and recurses only when the target is still reachable. The first step is restricted so that the entire square cannot be taken as a single block. As soon as one valid partition is found, the square is added to the running total.
Let \(R=\lfloor\sqrt{L}\rfloor\), and let \(d\) be the digit count of the square currently being tested. Without pruning, a single test can inspect up to \(2^{d-1}-1\) nontrivial partitions. The modulo \(9\) filter reduces the number of tested roots to about \(2R/9\), and the suffix bounds cut off many branches well before the leaves of the search tree.
Thus the worst-case time per tested root is still exponential in \(d\), but the practical runtime is much smaller because \(d\) is small and the pruning is strong. Memory usage is \(O(d)\): the digit list, the two suffix tables, and the recursion stack are all linear in the digit count.
Eine positive ganze Zahl \(n\) heißt S-Zahl, wenn \(n\) ein Quadrat ist und man die Dezimaldarstellung von \(n\) in mindestens zwei zusammenhängende Blöcke zerlegen kann, deren ganzzahlige Werte zusammen \(\sqrt{n}\) ergeben. Gesucht ist
$$T(L)=\sum_{\substack{n\le L\\ n\text{ ist eine S-Zahl}}} n.$$
Da jeder beitragende Term ein Quadrat ist, ist es günstiger, direkt über die Wurzeln \(r\) zu iterieren und zu prüfen, ob sich die Ziffern von \(r^2\) passend zerlegen lassen.
Mit \(\mathcal{S}\) als Menge der gültigen Wurzeln gilt also äquivalent
$$T(L)=\sum_{\substack{1\le r\le \lfloor\sqrt{L}\rfloor\\ r\in\mathcal{S}}} r^2.$$
Die Implementierung verbindet einen notwendigen Kongruenztest mit einer Tiefensuche über alle möglichen Schnittpositionen. Effizient wird diese Suche durch scharfe Unter- und Obergrenzen für jeden noch nicht verarbeiteten Ziffernsuffix.
Sei \(r\) eine Kandidatenwurzel und \(n=r^2\). Zerlege die Dezimaldarstellung von \(n\) in zusammenhängende Blöcke mit Werten \(b_1,b_2,\dots,b_k\), wobei \(k\ge2\) ist. Dann ist \(r\) genau dann gültig, wenn
$$b_1+b_2+\cdots+b_k=r.$$
Es werden keine Rechenzeichen eingefügt und keine Ziffern umgeordnet; nur die Schnittstellen zwischen den Ziffern werden gewählt. Hat \(n\) insgesamt \(d\) Ziffern, dann gibt es roh betrachtet \(2^{d-1}-1\) nichttriviale Zerlegungen.
Jede erfolgreiche Zerlegung erfüllt eine starke Kongruenz. Da für alle \(m\) gilt \(10^m\equiv1\pmod 9\), ändert das Zerschneiden einer Dezimalzahl in Blöcke ihren Wert modulo \(9\) nicht. Also ist die Summe der Blöcke kongruent zum ursprünglichen Quadrat:
$$r\equiv r^2\pmod 9.$$
Daraus folgt
$$r(r-1)\equiv0\pmod 9,$$
also zwingend
$$r\bmod 9\in\{0,1\}.$$
Diese Bedingung ist nur notwendig, aber nicht hinreichend. Dennoch entfernt sie bereits \(7/9\) aller Wurzeln, bevor die eigentliche Suche beginnt.
Angenommen, einige Anfangsblöcke wurden bereits gewählt und ihre Summe ist \(s\). Wähle nun den nächsten Block, sodass die neue Teilsumme \(s'\) entsteht. Der verbleibende Ziffernsuffix sei \(R\). Schreibe \(D(R)\) für die Summe seiner Ziffern und \(V(R)\) für den ganzzahligen Wert des gesamten Suffixes.
Jede Fortsetzung der Zerlegung muss dann im Intervall
$$[\,s'+D(R),\,s'+V(R)\,]$$
enden. Die Untergrenze entsteht, wenn zwischen allen restlichen Ziffern getrennt wird. Die Obergrenze entsteht, wenn gar nicht mehr getrennt wird und der gesamte Rest als ein Block gelesen wird. Daher kann ein Ast sofort verworfen werden, sobald
$$s'+D(R)\gt r$$
oder
$$s'+V(R)\lt r$$
gilt.
Nach der Wahl eines Kandidatenblocks wird dieselbe Logik auf die restlichen Ziffern angewandt. Überschreitet die laufende Summe bereits \(r\), endet der Ast sofort, denn alle Blockwerte sind nichtnegativ. Wird das Ende der Ziffernfolge erreicht, ist die Zerlegung genau dann erfolgreich, wenn die aufsummierten Blockwerte gleich \(r\) sind.
Die triviale Ein-Block-Zerlegung \(r^2\) selbst ist ausgeschlossen, weil die Definition mindestens zwei Teile verlangt. Die Implementierungen erzwingen das, indem der erste Block vor der letzten Ziffer enden muss; damit ist mindestens ein Schnitt garantiert.
Nehmen wir \(r=45\), also \(n=r^2=2025\). Der Modulo-9-Filter wird bestanden, denn \(45\equiv0\pmod 9\).
Ist der erste Block \(2\), dann bleibt der Suffix \(025\). Es gilt
$$2+(0+2+5)=9,\qquad 2+25=27.$$
Jede mögliche Fortsetzung liegt also zwischen \(9\) und \(27\) und kann niemals \(45\) erreichen. Dieser ganze Ast wird sofort abgeschnitten.
Ist der erste Block dagegen \(20\), so bleibt der Suffix \(25\). Das zulässige Intervall ist nun
$$[27,45].$$
Das Ziel liegt in diesem Intervall, und mit dem letzten Block \(25\) erhält man
$$20+25=45.$$
Damit ist \(2025\) eine S-Zahl und trägt \(2025\) zu \(T(L)\) bei.
Die Implementierungen in C++, Python und Java verwenden denselben Ablauf. Sie iterieren Kandidatenwurzeln \(r\) ab \(2\), brechen ab, sobald \(r^2\) die Grenze überschreitet, und verwerfen jede Wurzel, deren Restklasse modulo \(9\) weder \(0\) noch \(1\) ist.
Für jede verbleibende Wurzel wird das Quadrat \(r^2\) in eine Ziffernfolge umgewandelt. Danach werden zwei Suffix-Tabellen aufgebaut: eine speichert für jede Position den Zahlenwert des kompletten Rest-Suffixes, die andere die Ziffernsumme dieses Suffixes. So lässt sich der Intervalltest aus dem mathematischen Teil an jedem rekursiven Knoten in konstanter Zeit auswerten.
Anschließend probiert die Suche jeden möglichen nächsten Block, aktualisiert die Teilsumme, prüft die Unter- und Obergrenze und steigt nur dann tiefer hinab, wenn das Ziel noch erreichbar ist. Der erste Schritt ist so eingeschränkt, dass das Quadrat nicht als ein einziger Block genommen werden kann. Sobald eine gültige Zerlegung gefunden wurde, wird das Quadrat zur Gesamtsumme addiert.
Sei \(R=\lfloor\sqrt{L}\rfloor\), und sei \(d\) die Ziffernzahl des jeweils getesteten Quadrats. Ohne Pruning könnte ein einzelner Test bis zu \(2^{d-1}-1\) nichttriviale Zerlegungen untersuchen. Der Modulo-9-Filter reduziert die Zahl der tatsächlich geprüften Wurzeln auf ungefähr \(2R/9\), und die Suffix-Grenzen schneiden viele Äste lange vor den Blättern des Suchbaums ab.
Damit bleibt die Worst-Case-Laufzeit pro getesteter Wurzel zwar exponentiell in \(d\), praktisch ist sie aber deutlich kleiner, weil \(d\) klein ist und das Pruning stark wirkt. Der Speicherbedarf ist \(O(d)\): Ziffernfolge, die beiden Suffix-Tabellen und der Rekursionsstack sind alle linear in der Ziffernzahl.
Pozitif bir \(n\) sayısı, eğer \(n\) tam kare ise ve \(n\)'nin ondalık basamakları en az iki bitişik bloğa ayrılıp bu blokların tamsayı değerleri toplamı \(\sqrt{n}\) ediyorsa bir S-sayısıdır. İstenen büyüklük
$$T(L)=\sum_{\substack{n\le L\\ n\text{ bir S-sayısıdır}}} n$$
toplamıdır.
Katkı yapan her terim bir kare olduğu için, doğrudan \(n\) üzerinde değil, kök \(r\) üzerinde ilerlemek daha doğaldır. Yani asıl soru, \(r^2\)'nin ondalık gösteriminin uygun bir bölünmeye sahip olup olmadığıdır.
\(\mathcal{S}\) geçerli köklerin kümesi olmak üzere eşdeğer yazım
$$T(L)=\sum_{\substack{1\le r\le \lfloor\sqrt{L}\rfloor\\ r\in\mathcal{S}}} r^2$$
şeklindedir.
Uygulama, gerekli bir modüler ön filtre ile ondalık kesim noktaları üzerinde çalışan bir derinlik öncelikli aramayı birleştirir. Bu arama, kalan her son ek için güçlü alt ve üst sınırlar kurulduğu için verimli hale gelir.
\(r\) bir aday kök ve \(n=r^2\) olsun. \(n\)'nin ondalık gösterimini, değerleri \(b_1,b_2,\dots,b_k\) olan bitişik bloklara ayıralım; burada \(k\ge2\) olmalıdır. O zaman \(r\) ancak ve ancak
$$b_1+b_2+\cdots+b_k=r$$
ise geçerlidir.
Burada ne işlem işareti eklenir ne de basamaklar yer değiştirir; yalnızca kesim yerleri seçilir. Eğer \(n\) sayısı \(d\) basamaklıysa, komşu basamaklar arasındaki her boşluk için kes ya da kesme kararı verilir. Dolayısıyla ham arama uzayında \(2^{d-1}-1\) adet tek parça dışı bölme vardır.
Başarılı her bölme güçlü bir kongruens şartı taşır. Her \(m\) için \(10^m\equiv1\pmod 9\) olduğundan, bir ondalık diziyi bloklara bölmek sayının mod \(9\) değerini değiştirmez. Bu yüzden blokların toplamı ilk karenin kendisiyle mod \(9\) bakımından aynıdır:
$$r\equiv r^2\pmod 9.$$
Bu da
$$r(r-1)\equiv0\pmod 9$$
demektir ve zorunlu olarak
$$r\bmod 9\in\{0,1\}$$
olmasını gerektirir. Bu koşul yeterli değildir, ama arama başlamadan önce adayların \(7/9\)'unu eler.
Diyelim ki bazı başlangıç blokları seçildi ve toplamları \(s\) oldu. Şimdi bir blok daha seçildiğinde yeni kısmi toplam \(s'\) olsun. Kullanılmamış son ek \(R\) ile gösterilsin. \(D(R)\), bu son ekin basamak toplamı; \(V(R)\) ise tüm son ek tek sayı olarak okunursa elde edilen değerdir.
Bundan sonra elde edilebilecek nihai toplam mutlaka
$$[\,s'+D(R),\,s'+V(R)\,]$$
aralığındadır. Alt sınır, kalan her basamağın ayrı blok yapılmasıyla oluşur. Üst sınır ise artık hiç kesim yapılmayıp tüm son ekin tek blok alınmasıyla oluşur. Bu nedenle aşağıdaki durumlardan biri varsa dal hemen budanır:
$$s'+D(R)\gt r$$
veya
$$s'+V(R)\lt r.$$
Bir aday blok seçildikten sonra aynı mantık kalan basamaklara uygulanır. Ara toplam zaten \(r\)'yi geçmişse dal durur; çünkü tüm blok değerleri negatif olmayan sayılardır. Basamak dizisinin sonuna ulaşıldığında başarı koşulu, birikmiş toplamın tam olarak \(r\) olmasıdır.
Tek blokluk önemsiz bölme, yani doğrudan \(r^2\), kabul edilmez; çünkü tanım en az iki parça ister. Uygulamalar bunu, ilk bloğun son basamaktan önce bitmesini zorunlu kılarak yapar. Böylece en az bir kesim garanti edilir.
\(r=45\) olsun; o halde \(n=r^2=2025\). Modüler filtre geçilir, çünkü \(45\equiv0\pmod 9\).
İlk blok \(2\) seçilirse kalan son ek \(025\) olur. Bu durumda
$$2+(0+2+5)=9,\qquad 2+25=27.$$
Yani devam eden her yolun toplamı \(9\) ile \(27\) arasında kalır ve hiçbir zaman \(45\)'e ulaşamaz. Bu dal anında budanır.
İlk blok \(20\) seçilirse son ek \(25\) olur. Bu kez mümkün aralık
$$[27,45]$$
şeklindedir. Hedef bu aralığın içindedir ve son blok \(25\) seçildiğinde
$$20+25=45$$
elde edilir. Dolayısıyla \(2025\) bir S-sayısıdır ve \(T(L)\) toplamına \(2025\) katkı yapar.
C++, Python ve Java implementasyonları aynı akışı izler. \(r\) aday kökleri \(2\)'den başlayarak dolaşırlar, \(r^2\) üst sınıra geçtiğinde dururlar ve mod \(9\) kalanı \(0\) ya da \(1\) olmayan her kökü doğrudan elerler.
Kalan her kök için \(r^2\), bir basamak dizisine çevrilir. Ardından iki son ek tablosu hazırlanır: biri her pozisyondan başlayan son ekin tam sayı değerini, diğeri aynı son ekin basamak toplamını tutar. Böylece matematik bölümündeki aralık testi, aramanın her düğümünde sabit zamanda yapılabilir.
Arama daha sonra her olası yeni bloğu dener, ara toplamı günceller, alt ve üst sınırları kontrol eder ve hedef hâlâ erişilebilir görünüyorsa derine iner. İlk adım özellikle kısıtlanır; böylece tüm kare tek blok olarak alınamaz. Geçerli tek bir bölme bulunur bulunmaz kare toplamın içine eklenir.
\(R=\lfloor\sqrt{L}\rfloor\) olsun ve test edilen karenin basamak sayısı \(d\) olsun. Budama olmasa, tek bir kontrol en fazla \(2^{d-1}-1\) adet tek parça dışı bölmeyi inceleyebilir. Mod \(9\) filtresi gerçekten denenmesi gereken kök sayısını yaklaşık \(2R/9\) düzeyine indirir; son ek sınırları da arama ağacının birçok dalını yapraklara ulaşmadan keser.
Böylece test edilen her kök için en kötü durum süresi hâlâ \(d\) cinsinden üsteldir, fakat pratik çalışma süresi çok daha düşüktür; çünkü \(d\) küçüktür ve budama güçlüdür. Bellek kullanımı \(O(d)\)'dir: basamak dizisi, iki son ek tablosu ve özyineleme yığını hep basamak sayısıyla doğrusal büyür.
Un entero positivo \(n\) se llama S-number si \(n\) es un cuadrado perfecto y los dígitos decimales de \(n\) pueden cortarse en al menos dos bloques contiguos cuyas sumas de valores enteros dan exactamente \(\sqrt{n}\). Se pide calcular
$$T(L)=\sum_{\substack{n\le L\\ n\text{ es un S-number}}} n.$$
Como todos los términos que contribuyen son cuadrados, resulta más natural iterar sobre las raíces \(r\) y preguntar si la expansión decimal de \(r^2\) admite una partición válida.
Si \(\mathcal{S}\) denota el conjunto de raíces válidas, entonces
$$T(L)=\sum_{\substack{1\le r\le \lfloor\sqrt{L}\rfloor\\ r\in\mathcal{S}}} r^2.$$
La implementación combina un filtro de congruencia necesario con una búsqueda en profundidad sobre las posiciones posibles de corte. La búsqueda se vuelve práctica gracias a cotas inferiores y superiores muy ajustadas para cada sufijo aún no procesado.
Sea \(r\) una raíz candidata y \(n=r^2\). Dividamos la expansión decimal de \(n\) en bloques contiguos con valores \(b_1,b_2,\dots,b_k\), con \(k\ge2\). Entonces \(r\) es válida exactamente cuando
$$b_1+b_2+\cdots+b_k=r.$$
No se insertan operadores ni se reordenan los dígitos; únicamente se eligen puntos de corte. Si \(n\) tiene \(d\) dígitos, cada hueco entre dígitos consecutivos puede cortarse o no, de modo que el espacio bruto de búsqueda contiene \(2^{d-1}-1\) particiones no triviales.
Toda partición exitosa satisface una congruencia fuerte. Como \(10^m\equiv1\pmod 9\) para todo \(m\), cortar una cadena decimal en bloques no cambia su valor módulo \(9\). Por tanto, la suma de los bloques es congruente con el cuadrado original:
$$r\equiv r^2\pmod 9.$$
Esto equivale a
$$r(r-1)\equiv0\pmod 9,$$
y obliga a que
$$r\bmod 9\in\{0,1\}.$$
La condición no es suficiente, pero sí elimina \(7/9\) de todas las raíces antes de empezar la búsqueda recursiva.
Supongamos que ya se eligieron algunos bloques iniciales y que su suma es \(s\). Al elegir un bloque más, la nueva suma parcial pasa a ser \(s'\). Sea \(R\) el sufijo que aún queda por usar. Denotemos por \(D(R)\) la suma de sus dígitos y por \(V(R)\) el valor entero del sufijo completo.
Cualquier continuación válida debe terminar en el intervalo
$$[\,s'+D(R),\,s'+V(R)\,].$$
La cota inferior aparece al cortar entre todos los dígitos restantes. La cota superior aparece al no hacer más cortes y tomar todo el sufijo como un único bloque. Por ello, una rama se descarta de inmediato si
$$s'+D(R)\gt r$$
o si
$$s'+V(R)\lt r.$$
Después de elegir un bloque candidato, la misma lógica se aplica al resto de los dígitos. Si la suma acumulada ya supera \(r\), la rama termina porque todos los bloques son no negativos. Cuando se alcanza el final de la cadena decimal, la partición es correcta si y solo si la suma acumulada coincide exactamente con \(r\).
La partición trivial de un solo bloque, es decir, \(r^2\) completo, debe excluirse porque la definición exige al menos dos partes. Las implementaciones lo garantizan forzando que el primer bloque termine antes del último dígito.
Tomemos \(r=45\), de modo que \(n=r^2=2025\). El filtro modular se supera porque \(45\equiv0\pmod 9\).
Si el primer bloque es \(2\), el sufijo restante es \(025\). Entonces
$$2+(0+2+5)=9,\qquad 2+25=27.$$
Así, cualquier continuación queda entre \(9\) y \(27\), de modo que nunca podrá llegar a \(45\). Toda esa rama se poda inmediatamente.
Si el primer bloque es \(20\), el sufijo es \(25\). Ahora el intervalo factible es
$$[27,45].$$
El objetivo está dentro del intervalo, y al tomar el último bloque como \(25\) se obtiene
$$20+25=45.$$
Por tanto, \(2025\) es un S-number y aporta \(2025\) a \(T(L)\).
Las implementaciones en C++, Python y Java siguen exactamente la misma estructura. Recorren raíces candidatas \(r\) desde \(2\), se detienen cuando \(r^2\) supera el límite y rechazan de inmediato toda raíz cuyo residuo módulo \(9\) no sea ni \(0\) ni \(1\).
Para cada raíz que sobrevive, el cuadrado \(r^2\) se convierte en una secuencia de dígitos. Después se preparan dos tablas de sufijos: una guarda el valor numérico del sufijo completo desde cada posición y la otra guarda la suma de los dígitos de ese mismo sufijo. Con eso, la prueba de intervalo del apartado matemático se evalúa en tiempo constante en cada nodo de la recursión.
La búsqueda prueba cada posible siguiente bloque, actualiza la suma parcial, aplica las cotas inferior y superior y solo continúa si el objetivo sigue siendo alcanzable. El primer paso está restringido para impedir que todo el cuadrado se tome como un único bloque. En cuanto aparece una partición válida, el cuadrado se añade a la suma global.
Sea \(R=\lfloor\sqrt{L}\rfloor\), y sea \(d\) el número de dígitos del cuadrado que se está comprobando. Sin poda, una sola comprobación puede inspeccionar hasta \(2^{d-1}-1\) particiones no triviales. El filtro módulo \(9\) reduce el número de raíces realmente probadas a aproximadamente \(2R/9\), y las cotas sobre sufijos eliminan muchas ramas mucho antes de llegar a las hojas del árbol de búsqueda.
En consecuencia, el peor caso por raíz probada sigue siendo exponencial en \(d\), pero el tiempo práctico es bastante menor porque \(d\) es pequeño y la poda es fuerte. El uso de memoria es \(O(d)\): la lista de dígitos, las dos tablas de sufijos y la pila recursiva crecen linealmente con el número de dígitos.
若正整数 \(n\) 是完全平方数，并且 \(n\) 的十进制表示可以切成至少两个连续块，使这些块对应的整数之和恰好等于 \(\sqrt{n}\)，那么 \(n\) 就称为一个 S-number。题目要求计算
$$T(L)=\sum_{\substack{n\le L\\ n\text{ 是 S-number}}} n.$$
由于所有有贡献的数都是平方数，直接枚举 \(n\) 并不自然。更合适的做法是枚举平方根 \(r\)，再判断 \(r^2\) 的十进制数字是否存在满足条件的切分。
如果用 \(\mathcal{S}\) 表示所有合法平方根的集合，那么也可以写成
$$T(L)=\sum_{\substack{1\le r\le \lfloor\sqrt{L}\rfloor\\ r\in\mathcal{S}}} r^2.$$
实现采用两层思路：先用一个必要的模 \(9\) 条件快速过滤绝大多数根，再对剩余候选做十进制切分的深度优先搜索。搜索之所以可行，是因为对任意尚未处理的后缀，都能立即给出一个可靠的最小可达值和最大可达值。
设 \(r\) 是候选平方根，令 \(n=r^2\)。把 \(n\) 的十进制表示切成若干个连续块，其整数值记为 \(b_1,b_2,\dots,b_k\)，并且要求 \(k\ge2\)。那么 \(r\) 合法，当且仅当
$$b_1+b_2+\cdots+b_k=r.$$
这里没有插入加号之外的任何运算，也没有重排数字，本质上只是选择切口位置。若 \(n\) 有 \(d\) 位，那么相邻数字之间共有 \(d-1\) 个空隙，每个空隙都可以“切”或“不切”，因此原始搜索空间一共有 \(2^{d-1}-1\) 个非平凡划分。
凡是能够成功切分的情况，都必须满足一个很强的同余条件。原因是对任意 \(m\) 都有 \(10^m\equiv1\pmod 9\)，因此把一个十进制串切成若干块，不会改变它在模 \(9\) 下的值。于是块值之和与原平方数同余：
$$r\equiv r^2\pmod 9.$$
化简后得到
$$r(r-1)\equiv0\pmod 9,$$
所以必然有
$$r\bmod 9\in\{0,1\}.$$
这是必要条件而不是充分条件，但它已经能在真正搜索之前删掉 \(7/9\) 的候选根，因此收益极高。
假设前面若干块已经确定，它们的和为 \(s\)。现在再选一个新块，新的部分和变成 \(s'\)。把尚未使用的十进制后缀记作 \(R\)。记 \(D(R)\) 为后缀各位数字之和，记 \(V(R)\) 为把整个后缀当成一个整数时的数值。
那么后续无论怎样继续切分，最终总和一定落在区间
$$[\,s'+D(R),\,s'+V(R)\,]$$
之内。下界来自“把后缀每一位都单独切开”，因为一个十进制块的数值不会小于其数字和；上界来自“后缀不再切分”，即把整个后缀当成最后一个块。因此，只要出现下列任一情况，这个搜索分支就不可能成功：
$$s'+D(R)\gt r$$
或
$$s'+V(R)\lt r.$$
这两个判断都是确定性的，不需要继续深入就能立刻剪枝。
每确定一个候选块后，就对剩余数字递归地重复同样的过程。如果当前部分和已经超过 \(r\)，则该分支可以立即结束，因为后面加入的块都是非负整数，只会让总和更大。若递归走到数字串末尾，则只有在累计和恰好等于 \(r\) 时，这次切分才算成功。
此外，还必须排除“整个 \(r^2\) 作为一个块”的平凡情况，因为题目要求至少两个部分。实现中的做法是限制第一块不能一直延伸到最后一位，从而保证至少存在一个切口。
取 \(r=45\)，于是 \(n=r^2=2025\)。因为 \(45\equiv0\pmod 9\)，它先通过模 \(9\) 过滤。
如果第一块取成 \(2\)，剩余后缀是 \(025\)。这时有
$$2+(0+2+5)=9,\qquad 2+25=27.$$
也就是说，无论后面怎么切，最后总和都只能落在 \(9\) 到 \(27\) 之间，根本不可能达到目标 \(45\)。所以这一整支搜索立即被剪掉。
如果第一块取成 \(20\)，剩余后缀是 \(25\)。这时可达区间变成
$$[27,45].$$
目标 \(45\) 落在这个区间内，而把最后一块取为 \(25\) 时，恰好得到
$$20+25=45.$$
因此 \(2025\) 确实是一个 S-number，它会把 \(2025\) 本身贡献到 \(T(L)\) 里。
C++、Python 和 Java 实现遵循同一条流程。它们从 \(2\) 开始枚举候选根 \(r\)，一旦 \(r^2\) 超过上限就停止，并且先用模 \(9\) 条件排除余数既不是 \(0\) 也不是 \(1\) 的所有根。
对每个保留下来的根，程序先把平方 \(r^2\) 转成数字序列，然后建立两张后缀表：一张记录从每个位置开始的整个后缀作为整数时的值，另一张记录同一后缀的数字和。这样，数学部分给出的区间判定就可以在递归的每个节点上用常数时间完成。
随后，搜索会尝试当前位置能取出的每一个下一块，更新部分和，检查上下界是否仍然覆盖目标值，只有在“目标仍可能达到”时才继续向下递归。第一步专门受到限制，以防止整个平方数被当成单独一个块。只要找到任意一个合法切分，这个平方就会加入总和。
设 \(R=\lfloor\sqrt{L}\rfloor\)，设当前被检查平方数的位数为 \(d\)。如果完全不剪枝，那么一次检查最多需要查看 \(2^{d-1}-1\) 个非平凡切分。模 \(9\) 过滤把真正需要进入搜索的根数量压缩到大约 \(2R/9\)，而后缀上下界又会在搜索树很浅的位置剪掉大量不可能的分支。
因此，从理论最坏情况看，每个被测试的根仍可能需要指数级时间；但在实际运行中，\(d\) 很小，而且剪枝非常强，速度会快得多。空间复杂度是 \(O(d)\)：数字数组、两张后缀表以及递归栈都只与位数线性相关。
Положительное число \(n\) называется S-числом, если \(n\) является точным квадратом и его десятичную запись можно разрезать как минимум на два подряд идущих блока так, чтобы сумма целых значений этих блоков была равна \(\sqrt{n}\). Требуется вычислить
$$T(L)=\sum_{\substack{n\le L\\ n\text{ является S-числом}}} n.$$
Поскольку каждый вклад в сумму сам является квадратом, удобнее перебирать не \(n\), а корни \(r\), и проверять, допускает ли число \(r^2\) нужное десятичное разбиение.
Если \(\mathcal{S}\) обозначает множество допустимых корней, то равносильно
$$T(L)=\sum_{\substack{1\le r\le \lfloor\sqrt{L}\rfloor\\ r\in\mathcal{S}}} r^2.$$
Реализация сочетает необходимый фильтр по модулю \(9\) с поиском в глубину по позициям разреза десятичной строки. Поиск становится эффективным благодаря жёстким нижним и верхним оценкам для любого ещё не использованного суффикса.
Пусть \(r\) — кандидат на корень, а \(n=r^2\). Разобьём десятичную запись числа \(n\) на подряд идущие блоки со значениями \(b_1,b_2,\dots,b_k\), где \(k\ge2\). Тогда \(r\) подходит тогда и только тогда, когда
$$b_1+b_2+\cdots+b_k=r.$$
Никаких операций не вставляется и цифры не переставляются; выбираются только места разреза. Если у числа \(n\) ровно \(d\) цифр, то между соседними цифрами есть \(d-1\) промежутков, каждый из которых либо разрезается, либо нет. Значит, исходное пространство поиска содержит \(2^{d-1}-1\) нетривиальных разбиений.
У любого успешного разбиения есть сильное сравнение по модулю \(9\). Для всех \(m\) выполнено \(10^m\equiv1\pmod 9\), поэтому разрезание десятичной строки на блоки не меняет её остаток по модулю \(9\). Следовательно, сумма блоков сравнима с исходным квадратом:
$$r\equiv r^2\pmod 9.$$
Отсюда получаем
$$r(r-1)\equiv0\pmod 9,$$
то есть обязательно
$$r\bmod 9\in\{0,1\}.$$
Это условие необходимо, но не достаточно. Тем не менее оно отсекает \(7/9\) всех корней ещё до запуска рекурсивного перебора.
Предположим, что несколько начальных блоков уже выбраны и их сумма равна \(s\). После выбора ещё одного блока новая частичная сумма становится \(s'\). Пусть \(R\) — ещё не использованный десятичный суффикс. Обозначим через \(D(R)\) сумму его цифр, а через \(V(R)\) — значение всего суффикса как одного целого числа.
Тогда любая допустимая достройка обязана закончиться внутри интервала
$$[\,s'+D(R),\,s'+V(R)\,].$$
Нижняя граница получается, если разрезать каждую оставшуюся цифру отдельно. Верхняя — если больше не делать разрезов и взять весь суффикс одним блоком. Поэтому ветвь можно немедленно отбросить, когда
$$s'+D(R)\gt r$$
или
$$s'+V(R)\lt r.$$
После выбора очередного блока тот же принцип применяется к оставшимся цифрам. Если накопленная сумма уже превысила \(r\), ветвь можно остановить сразу, потому что все блоки неотрицательны и дальше сумма только растёт. Когда достигается конец строки, разбиение считается успешным тогда и только тогда, когда накопленная сумма точно равна \(r\).
Тривиальный случай из одного блока, то есть само число \(r^2\), должен быть исключён: по условию требуется минимум два фрагмента. В реализациях это обеспечивается тем, что первый блок обязан закончиться до последней цифры.
Возьмём \(r=45\), тогда \(n=r^2=2025\). Фильтр по модулю \(9\) проходит, потому что \(45\equiv0\pmod 9\).
Если первый блок равен \(2\), то оставшийся суффикс — \(025\). В этом случае
$$2+(0+2+5)=9,\qquad 2+25=27.$$
Значит, любое продолжение даст сумму между \(9\) и \(27\) и никогда не достигнет \(45\). Вся эта ветвь сразу отсекается.
Если же первый блок равен \(20\), то остаётся суффикс \(25\). Тогда допустимый интервал таков:
$$[27,45].$$
Цель лежит внутри интервала, и при выборе последнего блока \(25\) получаем
$$20+25=45.$$
Следовательно, \(2025\) является S-числом и вносит вклад \(2025\) в \(T(L)\).
Реализации на C++, Python и Java используют одну и ту же схему. Они перебирают кандидаты \(r\), начиная с \(2\), останавливаются, когда \(r^2\) превышает предел, и заранее отбрасывают все корни, чей остаток по модулю \(9\) не равен \(0\) или \(1\).
Для каждого прошедшего кандидата квадрат \(r^2\) переводится в массив цифр. Затем строятся две таблицы суффиксов: одна хранит значение полного оставшегося суффикса для каждой позиции, другая — сумму цифр этого же суффикса. Благодаря этому интервальная проверка из математической части выполняется за постоянное время в каждой рекурсивной вершине.
Далее поиск перебирает каждый возможный следующий блок, обновляет частичную сумму, проверяет нижнюю и верхнюю границы и углубляется только в тех ветвях, где цель ещё достижима. Первый шаг специально ограничен, чтобы весь квадрат нельзя было взять одним блоком. Как только находится хотя бы одно корректное разбиение, квадрат прибавляется к общей сумме.
Пусть \(R=\lfloor\sqrt{L}\rfloor\), а \(d\) — число цифр квадрата, который сейчас проверяется. Без отсечений одна проверка может рассмотреть до \(2^{d-1}-1\) нетривиальных разбиений. Фильтр по модулю \(9\) уменьшает число реально тестируемых корней примерно до \(2R/9\), а оценки для суффиксов отсекают множество ветвей задолго до листьев дерева поиска.
Поэтому в худшем случае время на один тестируемый корень всё ещё экспоненциально по \(d\), но на практике оно заметно меньше: \(d\) мало, а pruning очень сильный. Память равна \(O(d)\): массив цифр, две суффиксные таблицы и стек рекурсии растут линейно по числу цифр.
يُسمّى العدد الصحيح الموجب \(n\) عددًا من نوع S إذا كان مربعًا كاملًا، وكان بالإمكان قطع تمثيله العشري إلى كتلتين متجاورتين على الأقل بحيث يكون مجموع القيم الصحيحة لهذه الكتل مساويًا لـ \(\sqrt{n}\). وإذا رمزنا إلى مجموعة هذه الأعداد التي لا تتجاوز \(L\) بالرمز \(\mathcal{N}(L)\)، فإن المطلوب هو حساب
$$T(L)=\sum_{n\in\mathcal{N}(L)} n.$$
وبما أن كل حد يساهم في المجموع هو مربع كامل، فمن الأنسب أن نبحث في الجذر \(r\) نفسه، ثم نختبر هل يمكن تقسيم \(r^2\) عشريًا بالطريقة المطلوبة.
إذا رمزنا إلى مجموعة الجذور الصحيحة المقبولة بـ \(\mathcal{S}\)، فيمكن إعادة كتابة المطلوب على الصورة
$$T(L)=\sum_{\substack{1\le r\le \lfloor\sqrt{L}\rfloor\\ r\in\mathcal{S}}} r^2.$$
تعتمد الفكرة على مرحلتين: شرط توافق سريع modulo \(9\)، ثم بحث عمقي على مواضع القطع داخل التمثيل العشري. ويصبح هذا البحث عمليًا لأن كل لاحقة غير مكتملة تمتلك حدًا أدنى وحدًا أقصى يمكن حسابهما فورًا.
ليكن \(r\) جذرًا مرشحًا، ولتكن \(n=r^2\). نقسم التمثيل العشري للعدد \(n\) إلى كتل متجاورة قيمها \(b_1,b_2,\dots,b_k\)، مع الشرط \(k\ge2\). عندئذ يكون \(r\) صالحًا إذا وفقط إذا تحقق
$$b_1+b_2+\cdots+b_k=r.$$
لا نُدخل عمليات جديدة ولا نعيد ترتيب الأرقام؛ نحن فقط نختار أماكن القطع. وإذا كان \(n\) يتكون من \(d\) خانات، فبين كل خانتين متجاورتين قرار: نقطع أو لا نقطع. لذلك فإن فضاء البحث الخام يحتوي على \(2^{d-1}-1\) تقسيمات غير تافهة.
كل تقسيم ناجح يحقق علاقة توافق قوية. فلكل \(m\) لدينا \(10^m\equiv1\pmod 9\)، وهذا يعني أن تقسيم السلسلة العشرية إلى كتل لا يغيّر قيمتها modulo \(9\). وبالتالي فإن مجموع الكتل يوافق المربع الأصلي:
$$r\equiv r^2\pmod 9.$$
ومنها نحصل على
$$r(r-1)\equiv0\pmod 9,$$
أي لا بد أن يكون
$$r\bmod 9\in\{0,1\}.$$
هذا الشرط لازم وليس كافيًا، لكنه مع ذلك يستبعد \(7/9\) من جميع الجذور قبل بدء البحث الفعلي.
افترض أن بعض الكتل الأولى قد اختيرت بالفعل، وكان مجموعها \(s\). بعد اختيار كتلة جديدة تصبح القيمة الجزئية \(s'\). ولتكن \(R\) هي اللاحقة العشرية التي لم تُستعمل بعد. نرمز بـ \(D(R)\) إلى مجموع أرقام هذه اللاحقة، وبـ \(V(R)\) إلى قيمتها إذا قُرئت كعدد واحد كامل.
أي إكمال لاحق للتقسيم يجب أن ينتهي داخل المجال
$$[\,s'+D(R),\,s'+V(R)\,].$$
الحد الأدنى ينتج من قطع كل رقم متبقٍ على حدة، أما الحد الأقصى فينتج من عدم إجراء أي قطع جديد واعتبار اللاحقة كلها كتلة واحدة. لذلك يمكن حذف أي فرع فورًا إذا تحقق
$$s'+D(R)\gt r$$
أو
$$s'+V(R)\lt r.$$
بعد اختيار كتلة مرشحة، يُعاد تطبيق المنطق نفسه على بقية الخانات. وإذا كان المجموع الجزئي قد تجاوز \(r\) بالفعل، فيمكن إيقاف الفرع مباشرة لأن قيم الكتل غير سالبة ولن ينخفض المجموع لاحقًا. وعند الوصول إلى نهاية السلسلة الرقمية، ينجح التقسيم إذا وفقط إذا كان المجموع المتراكم مساويًا تمامًا لـ \(r\).
كما يجب استبعاد الحالة التافهة التي تؤخذ فيها \(r^2\) كلها كتلة واحدة، لأن التعريف يشترط جزأين على الأقل. لذلك تفرض التنفيذات أن تنتهي الكتلة الأولى قبل الخانة الأخيرة، وبذلك يصبح وجود قطع واحد على الأقل أمرًا مضمونًا.
خذ \(r=45\)، وعندئذ \(n=r^2=2025\). يمر هذا الجذر عبر مرشح modulo \(9\) لأن \(45\equiv0\pmod 9\).
إذا كانت الكتلة الأولى هي \(2\)، فاللاحقة المتبقية هي \(025\). عندها يكون
$$2+(0+2+5)=9,\qquad 2+25=27.$$
أي إن أي إكمال ممكن سيبقى بين \(9\) و\(27\)، ولن يصل أبدًا إلى الهدف \(45\). لذا يُقص هذا الفرع فورًا.
أما إذا كانت الكتلة الأولى هي \(20\)، فاللاحقة تصبح \(25\). عندئذ يكون المجال الممكن
$$[27,45].$$
والهدف يقع داخل هذا المجال، كما أن اختيار الكتلة الأخيرة \(25\) يعطي
$$20+25=45.$$
ومن ثم فإن \(2025\) عدد من نوع S، ويساهم بالقيمة \(2025\) في \(T(L)\).
تتبع تنفيذات C++ وPython وJava البنية نفسها. فهي تمر على الجذور المرشحة \(r\) بدءًا من \(2\)، وتتوقف عندما يصبح \(r^2\) أكبر من الحد المطلوب، وتستبعد مباشرة كل جذر لا يكون باقيه modulo \(9\) مساويًا لـ \(0\) أو \(1\).
لكل جذر ينجو من هذا الفلتر، تُحوَّل قيمة \(r^2\) إلى سلسلة من الخانات. ثم تُبنى جدولان للواحق: أحدهما يحفظ قيمة كل لاحقة كاملة إذا قُرئت كعدد واحد، والآخر يحفظ مجموع أرقام تلك اللاحقة. وبهذا تصبح فحوص المجال المذكورة في القسم الرياضي قابلة للتنفيذ بزمن ثابت في كل عقدة من عقد البحث.
بعد ذلك يجرّب البحث كل كتلة تالية ممكنة، ويحدّث المجموع الجزئي، ويفحص الحدين الأدنى والأقصى، ولا يتابع إلا إذا كان الوصول إلى الهدف لا يزال ممكنًا. كما تُقيَّد الخطوة الأولى بحيث لا يمكن أخذ المربع كله ككتلة واحدة. وبمجرد العثور على تقسيم صالح واحد، يُضاف المربع إلى المجموع الكلي.
ليكن \(R=\lfloor\sqrt{L}\rfloor\)، ولتكن \(d\) عدد خانات المربع الجاري اختباره. من دون أي قص، قد يفحص اختبار واحد ما يصل إلى \(2^{d-1}-1\) تقسيمًا غير تافه. ويقلل شرط modulo \(9\) عدد الجذور التي تدخل البحث فعليًا إلى نحو \(2R/9\)، ثم تأتي حدود اللواحق لتقص كثيرًا من الفروع قبل الوصول إلى أوراق شجرة البحث.
لذلك يبقى حد الزمن الأسوأ لكل جذر مختبَر أسيًا في \(d\)، لكن الزمن العملي أقل بكثير لأن \(d\) صغير والقص قوي. أما الذاكرة فهي \(O(d)\): قائمة الخانات، وجدولا اللواحق، ومكدس الاستدعاء جميعها تنمو خطيًا مع عدد الخانات.