We seek square numbers \(n\) below \(10^{16}\) whose decimal expansion can be split into a nonempty left part and a nonempty right part so that the square root is the sum of those two parts. Writing \(n=s^2\), the split has the form
$$n=a10^d+b,\qquad s=a+b,$$
where \(b\) has exactly \(d\) digits. The title example is \(2025=20\mid 25\), because \(20+25=45=\sqrt{2025}\). The task is to add all such squares, not all successful splits, so duplicates must be counted only once.
This is closely related to base-10 Kaprekar numbers, but the efficient way to solve the Project Euler problem is to search over the root \(s\) and describe the allowed values of \(s\) by modular arithmetic.
Fix a split length \(d\) and write
$$M_d=10^d-1.$$
For that fixed \(d\), the whole problem is to characterize the roots \(s\) for which the split exists.
From \(n=s^2=a10^d+b\) and \(s=a+b\), substitute \(b=s-a\):
$$s^2=a10^d+(s-a)=s+a(10^d-1).$$
Therefore
$$a=\frac{s(s-1)}{M_d},\qquad b=s-a.$$
This already gives the key divisibility condition
$$M_d\mid s(s-1).$$
Once \(a\) is an integer and the digit conditions hold, the reconstruction is automatic, because
$$a10^d+b=a(10^d-1)+s=s(s-1)+s=s^2.$$
So the search is not really over \((a,b)\); it is over roots \(s\) satisfying one congruence and a few digit inequalities.
Factor \(M_d\) into pairwise coprime prime powers:
$$M_d=\prod_{i=1}^{t} p_i^{e_i}.$$
Consecutive integers are coprime, so \(\gcd(s,s-1)=1\). If \(p_i^{e_i}\) divides the product \(s(s-1)\), then the full prime power must divide exactly one of the two consecutive factors. Hence every valid root satisfies
$$s\equiv 0,1 \pmod{p_i^{e_i}},\qquad 1\le i\le t.$$
That is the crucial structural simplification. Instead of examining all roots below \(10^8\), we only have to choose, for every distinct prime-power factor of \(10^d-1\), whether \(s\) is congruent to \(0\) or to \(1\).
Each prime power contributes two local options, so a fixed \(d\) leads to a collection of global residue classes. The Chinese remainder theorem merges those local choices into unique congruences
$$s\equiv r \pmod{M_d}.$$
Every admissible root for that split length lies in one arithmetic progression
$$s=r+kM_d,\qquad k\ge 0.$$
The implementations therefore build all CRT residue classes first and only then test the corresponding candidate roots.
The modular condition is necessary, but not sufficient. We still need the split to be a genuine decimal split with both parts nonzero and with no leading zeros in the right block.
Because \(b=s-a\gt 0\), we need \(a\lt s\). Using the formula for \(a\),
$$\frac{s(s-1)}{M_d}\lt s,$$
which simplifies to
$$s\lt 10^d.$$
So every valid root must satisfy
$$2\le s\le \min\!\bigl(\lfloor\sqrt{10^{16}-1}\rfloor,\;10^d-1\bigr).$$
There is also an exact range for the right part:
$$1\le b\lt 10 \quad(d=1),\qquad 10^{d-1}\le b\lt 10^d \quad(d\ge 2).$$
The second condition is what rules out right parts such as \(01\) or \(0017\): they are numerically positive, but they do not occupy exactly \(d\) digits.
Take \(d=2\). Then
$$M_2=10^2-1=99=9\cdot 11.$$
For the prime powers \(9\) and \(11\), the only local residues are \(0\) and \(1\). CRT therefore produces four global residue classes modulo \(99\):
$$s\equiv 0,\ 1,\ 45,\ 55 \pmod{99}.$$
Since \(s\lt 100\), only the representatives \(45\), \(55\), and \(99\) can matter.
For \(s=45\),
$$a=\frac{45\cdot 44}{99}=20,\qquad b=45-20=25,$$
so \(45^2=2025=20\mid 25\).
For \(s=55\),
$$a=\frac{55\cdot 54}{99}=30,\qquad b=55-30=25,$$
so \(55^2=3025=30\mid 25\).
For \(s=99\),
$$a=\frac{99\cdot 98}{99}=98,\qquad b=1,$$
but \(b=1\) is not a two-digit number, so the split \(98\mid 01\) is invalid. This example shows exactly why the algorithm needs both pieces: CRT generates the modular candidates, and the digit checks remove the false positives.
The Project Euler question asks for the sum of the numbers \(n\), not the sum over all successful pairs \((n,d)\). A square can satisfy the defining property for more than one split length, so the accepted values \(n=s^2\) must be stored as distinct integers before the final addition is performed.
The C++, Python, and Java implementations precompute powers of \(10\), the root bound \(\lfloor\sqrt{10^{16}-1}\rfloor\), and a prime table large enough to factor every repunit-like modulus \(10^d-1\) with \(1\le d\le 15\).
For each split length \(d\), the implementation factors \(10^d-1\) into prime powers. It starts from the trivial congruence modulo \(1\) and repeatedly merges the two local possibilities \(s\equiv0\) and \(s\equiv1\) modulo each prime power. After all merges, the result is the complete CRT list of admissible residues \(r\) modulo \(10^d-1\).
Each residue class produces a candidate root \(s\) in the allowed range. From that root, the implementation computes \(a=\frac{s(s-1)}{10^d-1}\), then \(b=s-a\), checks positivity, checks the exact digit range of \(b\), reconstructs \(n=s^2\), and inserts \(n\) into a hash set. The C++ implementation also includes small direct-search self-checks for shorter digit limits before producing the final \(10^{16}\) answer.
Let \(\omega(M_d)\) be the number of distinct prime divisors of \(M_d=10^d-1\). For a fixed \(d\), the CRT stage creates exactly \(2^{\omega(M_d)}\) residue classes, because each prime power contributes the binary choice \(0\) or \(1\).
For this particular problem size, the bound \(s\lt 10^d\) means that each residue class contributes at most one relevant root candidate. As a result, after factorization the remaining work is essentially one constant-time arithmetic check per CRT residue. Memory usage is small: a prime list, a temporary residue list, and the set of accepted squares. This is far smaller than a naive search over all roots up to \(10^8\) and all possible split positions.
Gesucht sind Quadratzahlen \(n\lt 10^{16}\), deren Dezimalschreibweise sich in einen nichtleeren linken Teil und einen nichtleeren rechten Teil zerlegen lässt, so dass die Quadratwurzel die Summe dieser beiden Teile ist. Mit \(n=s^2\) hat die Zerlegung die Form
$$n=a10^d+b,\qquad s=a+b,$$
wobei \(b\) genau \(d\) Stellen besitzt. Das Titelbeispiel ist \(2025=20\mid 25\), denn \(20+25=45=\sqrt{2025}\). Gesucht ist die Summe aller solchen Quadrate; tritt dieselbe Zahl bei mehreren Schnittlängen auf, darf sie nur einmal gezählt werden.
Das steht in enger Beziehung zu Kaprekar-Zahlen in Basis 10. Für die eigentliche Berechnung ist es jedoch viel günstiger, nicht die Quadrate \(n\), sondern direkt ihre Wurzeln \(s\) per modularer Arithmetik zu beschreiben.
Für eine feste Schnittlänge \(d\) setzen wir
$$M_d=10^d-1.$$
Dann reduziert sich das Problem darauf, alle Wurzeln \(s\) zu charakterisieren, für die ein gültiger Dezimalschnitt existiert.
Aus \(n=s^2=a10^d+b\) und \(s=a+b\) folgt mit \(b=s-a\):
$$s^2=a10^d+(s-a)=s+a(10^d-1).$$
Also gilt
$$a=\frac{s(s-1)}{M_d},\qquad b=s-a.$$
Damit erhalten wir sofort die zentrale Teilbarkeitsbedingung
$$M_d\mid s(s-1).$$
Sobald \(a\) ganzzahlig ist und die Stellenbedingungen erfüllt sind, ist die Rekonstruktion automatisch richtig, denn
$$a10^d+b=a(10^d-1)+s=s(s-1)+s=s^2.$$
Die eigentliche Suche läuft also nicht über alle möglichen Paare \((a,b)\), sondern über Wurzeln \(s\), die eine Kongruenz und einige Ziffernrestriktionen erfüllen.
Faktorisiere \(M_d\) in paarweise teilerfremde Primzahlpotenzen:
$$M_d=\prod_{i=1}^{t} p_i^{e_i}.$$
Da aufeinanderfolgende ganze Zahlen teilerfremd sind, ist \(\gcd(s,s-1)=1\). Wenn also \(p_i^{e_i}\) das Produkt \(s(s-1)\) teilt, dann muss die gesamte Primzahlpotenz entweder \(s\) oder \(s-1\) teilen. Jede gültige Wurzel erfüllt daher
$$s\equiv 0,1 \pmod{p_i^{e_i}},\qquad 1\le i\le t.$$
Das ist die entscheidende Vereinfachung: Statt alle Wurzeln unterhalb von \(10^8\) zu testen, wählt man für jede verschiedene Primzahlpotenz von \(10^d-1\) nur noch zwischen den beiden Resten \(0\) und \(1\).
Jede Primzahlpotenz liefert zwei lokale Optionen. Für ein festes \(d\) entsteht daraus eine Menge globaler Restklassen. Der chinesische Restsatz kombiniert die lokalen Wahlmöglichkeiten zu eindeutigen Kongruenzen
$$s\equiv r \pmod{M_d}.$$
Alle zulässigen Wurzeln zu dieser Schnittlänge liegen daher in einer arithmetischen Folge
$$s=r+kM_d,\qquad k\ge 0.$$
Die Implementierungen bauen also zuerst sämtliche CRT-Restklassen auf und testen danach nur noch die daraus entstehenden Kandidaten.
Die Kongruenz allein reicht noch nicht aus. Der Schnitt muss wirklich aus zwei positiven Dezimalblöcken bestehen, und der rechte Block darf keine führenden Nullen verstecken.
Weil \(b=s-a\gt 0\) gilt, brauchen wir \(a\lt s\). Mit der Formel für \(a\) wird daraus
$$\frac{s(s-1)}{M_d}\lt s,$$
also
$$s\lt 10^d.$$
Damit muss jede gültige Wurzel im Bereich
$$2\le s\le \min\!\bigl(\lfloor\sqrt{10^{16}-1}\rfloor,\;10^d-1\bigr)$$
liegen. Zusätzlich braucht der rechte Teil den exakten Stellenumfang
$$1\le b\lt 10 \quad(d=1),\qquad 10^{d-1}\le b\lt 10^d \quad(d\ge 2).$$
Die zweite Bedingung schließt Fälle wie \(01\) oder \(0017\) aus: numerisch positiv, aber eben kein rechter Block mit genau \(d\) Stellen.
Setze \(d=2\). Dann ist
$$M_2=10^2-1=99=9\cdot 11.$$
Für die Primzahlpotenzen \(9\) und \(11\) sind lokal nur die Reste \(0\) und \(1\) möglich. Mit CRT entstehen daher vier globale Klassen modulo \(99\):
$$s\equiv 0,\ 1,\ 45,\ 55 \pmod{99}.$$
Wegen \(s\lt 100\) sind nur die Repräsentanten \(45\), \(55\) und \(99\) relevant.
Für \(s=45\) erhält man
$$a=\frac{45\cdot 44}{99}=20,\qquad b=45-20=25,$$
also \(45^2=2025=20\mid 25\).
Für \(s=55\) gilt
$$a=\frac{55\cdot 54}{99}=30,\qquad b=55-30=25,$$
also \(55^2=3025=30\mid 25\).
Für \(s=99\) bekommt man
$$a=\frac{99\cdot 98}{99}=98,\qquad b=1,$$
aber \(b=1\) ist keine zweistellige Zahl. Der Schnitt \(98\mid 01\) ist daher verboten. Genau daran sieht man, wie die modulare Vorselektion und die Stellenprüfung zusammenarbeiten.
Gefragt ist die Summe der Zahlen \(n\), nicht die Summe aller erfolgreichen Paare \((n,d)\). Es kann vorkommen, dass dieselbe Quadratzahl für mehrere Schnittlängen funktioniert. Deshalb werden die akzeptierten Werte \(n=s^2\) als Menge unterschiedlicher Ganzzahlen gesammelt und erst danach summiert.
Die C++-, Python- und Java-Implementierungen berechnen zuerst die Zehnerpotenzen, die Schranke \(\lfloor\sqrt{10^{16}-1}\rfloor\) und eine Primtabelle, die groß genug ist, um jede Moduluszahl \(10^d-1\) für \(1\le d\le 15\) zu faktorisieren.
Für jedes \(d\) wird \(10^d-1\) in Primzahlpotenzen zerlegt. Ausgehend vom trivialen Modul \(1\) werden dann die beiden lokalen Möglichkeiten \(s\equiv0\) und \(s\equiv1\) modulo jeder Primzahlpotenz schrittweise zusammengeführt. Nach allen Fusionen liegt die vollständige CRT-Liste aller zulässigen Reste \(r\) modulo \(10^d-1\) vor.
Jede Restklasse liefert eine Kandidatenwurzel \(s\) im erlaubten Bereich. Daraus berechnet die Implementierung \(a=\frac{s(s-1)}{10^d-1}\), dann \(b=s-a\), prüft die Positivität, prüft die exakte Stellenzahl von \(b\), rekonstruiert \(n=s^2\) und legt \(n\) in einer Hash-Menge ab. Die C++-Version enthält zusätzlich kleine Selbsttests per Direktsuche für kürzere Stellenlängen, bevor das Ergebnis für \(10^{16}\) ausgegeben wird.
Sei \(\omega(M_d)\) die Anzahl verschiedener Primteiler von \(M_d=10^d-1\). Für ein festes \(d\) erzeugt die CRT-Phase genau \(2^{\omega(M_d)}\) Restklassen, weil jede Primzahlpotenz die binäre Wahl zwischen \(0\) und \(1\) beiträgt.
Für die konkrete Problemgröße bedeutet die Schranke \(s\lt 10^d\), dass jede Restklasse höchstens einen relevanten Wurzelkandidaten liefert. Nach der Faktorisierung bleibt also im Wesentlichen nur noch eine konstante Anzahl ganzzahliger Prüfungen pro CRT-Rest. Der Speicherbedarf ist klein: eine Primliste, eine temporäre Liste von Restklassen und die Menge der akzeptierten Quadrate. Das ist um Größenordnungen kleiner als ein naiver Test aller Wurzeln bis \(10^8\) mit allen möglichen Schnittpositionen.
Aranan sayılar \(10^{16}\)'dan küçük karelerdir. Bir sayı \(n=s^2\) için ondalık yazım bir sol parça ve bir sağ parça halinde ayrılabiliyorsa ve karekök bu iki parçanın toplamına eşitse sayı geçerlidir. Ayırma şu biçimdedir:
$$n=a10^d+b,\qquad s=a+b,$$
burada \(b\) tam olarak \(d\) basamaklıdır. Başlıktaki örnek \(2025=20\mid 25\) sayısıdır; çünkü \(20+25=45=\sqrt{2025}\). İstenen şey, böyle bütün kareleri toplamak ve aynı kare birden fazla ayırma uzunluğu için çalışıyorsa onu yalnızca bir kez saymaktır.
Bu yapı taban 10 Kaprekar sayılarıyla yakından ilişkilidir. Fakat verimli çözüm, kare \(n\)'leri dolaşmak yerine doğrudan kök \(s\) üzerinde çalışıp izin verilen \(s\) değerlerini modüler aritmetik ile tarif etmektir.
Sabit bir ayırma uzunluğu \(d\) için
$$M_d=10^d-1$$
tanımını yapalım. Böylece problem, o \(d\) için hangi köklerin \(s\) geçerli olabileceğini belirlemeye dönüşür.
\(n=s^2=a10^d+b\) ve \(s=a+b\) denklemlerinde \(b=s-a\) yazarsak
$$s^2=a10^d+(s-a)=s+a(10^d-1)$$
elde edilir. Buradan
$$a=\frac{s(s-1)}{M_d},\qquad b=s-a$$
çıkar. Dolayısıyla temel bölünebilme koşulu
$$M_d\mid s(s-1)$$
olmalıdır. \(a\) tam sayı olduğu ve basamak koşulları da sağlandığı anda yeniden kurulum otomatik olarak doğrudur, çünkü
$$a10^d+b=a(10^d-1)+s=s(s-1)+s=s^2.$$
Yani arama uzayı aslında \((a,b)\) çiftleri değil; tek bir kongruensi ve birkaç basamak eşitsizliğini sağlayan kökler \(s\)'dir.
\(M_d\)'yi birbirine aralarında asal olan asal kuvvetlere ayıralım:
$$M_d=\prod_{i=1}^{t} p_i^{e_i}.$$
Ardışık iki tamsayı aralarında asaldır; yani \(\gcd(s,s-1)=1\). O halde \(p_i^{e_i}\) sayısı \(s(s-1)\)'i bölüyorsa, bu asal kuvvetin tamamı ya \(s\)'yi ya da \(s-1\)'i bölmek zorundadır. Bu yüzden her geçerli kök için
$$s\equiv 0,1 \pmod{p_i^{e_i}},\qquad 1\le i\le t.$$
olmalıdır. Asıl sadeleşme burada gelir: \(10^8\)'e kadar bütün kökleri denemek yerine, \(10^d-1\)'in her farklı asal kuvvet çarpanı için yalnızca iki yerel seçenek kalır.
Her asal kuvvet iki yerel seçenek verdiği için sabit bir \(d\) için bir dizi küresel artık sınıfı oluşur. Çin kalan teoremi bu seçimleri tek bir kongruenste birleştirir:
$$s\equiv r \pmod{M_d}.$$
Böylece o ayırma uzunluğu için tüm aday kökler şu aritmetik dizilerde yer alır:
$$s=r+kM_d,\qquad k\ge 0.$$
Uygulamalar bu nedenle önce tüm CRT artık sınıflarını üretir, sonra yalnızca bunların verdiği kök adaylarını sınar.
Modüler koşul gerekli ama tek başına yeterli değildir. Ayırmanın gerçekten iki pozitif ondalık parçadan oluşması ve sağ blokta gizli baştaki sıfırlar bulunmaması gerekir.
\(b=s-a\gt 0\) olduğundan \(a\lt s\) olmalıdır. \(a\) formülünü kullanırsak
$$\frac{s(s-1)}{M_d}\lt s,$$
buradan da
$$s\lt 10^d$$
çıkar. Demek ki her geçerli kök
$$2\le s\le \min\!\bigl(\lfloor\sqrt{10^{16}-1}\rfloor,\;10^d-1\bigr)$$
aralığındadır. Sağ parça için tam basamak koşulu da şudur:
$$1\le b\lt 10 \quad(d=1),\qquad 10^{d-1}\le b\lt 10^d \quad(d\ge 2).$$
İkinci eşitsizlik \(01\), \(0017\) gibi durumları otomatik olarak dışlar: sayı pozitif olsa bile sağ blok tam olarak \(d\) basamaklı değildir.
\(d=2\) alalım. O zaman
$$M_2=10^2-1=99=9\cdot 11.$$
\(9\) ve \(11\) için yerel kalıntılar yalnızca \(0\) ve \(1\)'dir. CRT bu seçimlerden mod \(99\) altında dört küresel sınıf üretir:
$$s\equiv 0,\ 1,\ 45,\ 55 \pmod{99}.$$
\(s\lt 100\) olduğu için yalnızca \(45\), \(55\) ve \(99\) temsilcileri önemlidir.
\(s=45\) için
$$a=\frac{45\cdot 44}{99}=20,\qquad b=45-20=25,$$
dolayısıyla \(45^2=2025=20\mid 25\).
\(s=55\) için
$$a=\frac{55\cdot 54}{99}=30,\qquad b=55-30=25,$$
ve \(55^2=3025=30\mid 25\).
\(s=99\) için ise
$$a=\frac{99\cdot 98}{99}=98,\qquad b=1,$$
ama \(b=1\) iki basamaklı değildir; yani \(98\mid 01\) ayırması yasaktır. Bu tek örnek, CRT'nin adayları nasıl ürettiğini ve basamak filtresinin yanlış adayları nasıl elediğini açıkça gösterir.
Sorulan büyüklük başarılı \((n,d)\) çiftlerinin toplamı değil, sayıların \(n\) toplamıdır. Aynı kare birden fazla ayırma uzunluğu için koşulu sağlayabilir. Bu yüzden kabul edilen \(n=s^2\) değerleri son toplama girmeden önce bir kümede tekilleştirilir.
C++, Python ve Java uygulamaları önce \(10\) kuvvetlerini, \(\lfloor\sqrt{10^{16}-1}\rfloor\) sınırını ve \(1\le d\le 15\) için tüm \(10^d-1\) sayılarının çarpanlara ayrılmasına yetecek bir asal tablosunu hazırlar.
Her \(d\) için \(10^d-1\) asal kuvvetlere ayrılır. Sonra modül \(1\)'den başlanır ve her asal kuvvet için \(s\equiv0\) ile \(s\equiv1\) yerel seçenekleri sırayla birleştirilir. Bütün birleştirmeler tamamlandığında mod \(10^d-1\) altında izin verilen tüm \(r\) artık sınıfları elde edilmiş olur.
Her artık sınıfı, izin verilen aralıkta bir kök adayı \(s\) üretir. Uygulama buradan \(a=\frac{s(s-1)}{10^d-1}\) ve \(b=s-a\) değerlerini hesaplar; iki parçanın pozitif olduğunu, \(b\)'nin tam olarak \(d\) basamaklı olduğunu ve \(n=s^2\) yeniden kurulumunun doğru olduğunu doğrular; sonra \(n\)'yi bir hash kümesine ekler. C++ sürümü ayrıca daha küçük basamak sınırları için doğrudan arama ile iç doğrulamalar yapar.
\(M_d=10^d-1\) için \(\omega(M_d)\), farklı asal bölen sayısı olsun. Sabit bir \(d\) için CRT aşaması tam olarak \(2^{\omega(M_d)}\) adet artık sınıfı üretir; çünkü her asal kuvvet \(0\) ile \(1\) arasında ikili bir seçim verir.
Bu problem boyutunda \(s\lt 10^d\) sınırı nedeniyle her artık sınıfı en fazla bir anlamlı kök adayı verir. Dolayısıyla çarpanlara ayırma sonrasında kalan iş, CRT kalıntısı başına sabit sayıda tam sayı kontrolünden ibarettir. Bellek kullanımı da küçüktür: bir asal listesi, geçici bir artık listesi ve kabul edilen karelerin kümesi. Bu, \(10^8\)'e kadar tüm kökleri ve bütün olası ayırma noktalarını denemekten çok daha verimlidir.
Buscamos cuadrados \(n\lt 10^{16}\) cuya escritura decimal pueda partirse en una parte izquierda no vacía y una parte derecha no vacía, de modo que la raíz cuadrada sea la suma de ambas partes. Si escribimos \(n=s^2\), el corte tiene la forma
$$n=a10^d+b,\qquad s=a+b,$$
donde \(b\) tiene exactamente \(d\) cifras. El ejemplo del título es \(2025=20\mid 25\), porque \(20+25=45=\sqrt{2025}\). Hay que sumar todos esos cuadrados, contando cada valor de \(n\) una sola vez aunque funcione con más de una longitud de corte.
El problema está emparentado con los números de Kaprekar en base 10, pero la vía eficiente consiste en trabajar directamente con la raíz \(s\) y describir las raíces admisibles mediante congruencias.
Fijemos una longitud de corte \(d\) y definamos
$$M_d=10^d-1.$$
Para ese \(d\), todo se reduce a caracterizar las raíces \(s\) para las cuales existe una partición decimal válida.
Partimos de \(n=s^2=a10^d+b\) y \(s=a+b\). Sustituyendo \(b=s-a\), obtenemos
$$s^2=a10^d+(s-a)=s+a(10^d-1).$$
Por tanto,
$$a=\frac{s(s-1)}{M_d},\qquad b=s-a.$$
Esto impone inmediatamente la condición de divisibilidad
$$M_d\mid s(s-1).$$
Una vez que \(a\) es entero y se cumplen las restricciones de cifras, la reconstrucción queda garantizada, porque
$$a10^d+b=a(10^d-1)+s=s(s-1)+s=s^2.$$
En otras palabras, no hace falta buscar pares \((a,b)\) directamente; basta estudiar las raíces \(s\) que satisfacen una congruencia y unas pocas desigualdades decimales.
Factorizamos \(M_d\) en potencias primas coprimas entre sí:
$$M_d=\prod_{i=1}^{t} p_i^{e_i}.$$
Como enteros consecutivos son coprimos, \(\gcd(s,s-1)=1\). Si \(p_i^{e_i}\) divide al producto \(s(s-1)\), entonces toda esa potencia prima debe dividir exactamente a uno de los dos factores consecutivos. Así, toda raíz válida cumple
$$s\equiv 0,1 \pmod{p_i^{e_i}},\qquad 1\le i\le t.$$
Esa es la reducción decisiva: en vez de probar todas las raíces hasta \(10^8\), solo hay que escoger, para cada potencia prima distinta de \(10^d-1\), si \(s\) cae en el residuo \(0\) o en el residuo \(1\).
Cada potencia prima aporta dos opciones locales, de modo que para un \(d\) fijo aparece una familia de clases residuales globales. El teorema chino del resto combina esas elecciones en congruencias únicas
$$s\equiv r \pmod{M_d}.$$
Todas las raíces admisibles para esa longitud de corte pertenecen a una progresión aritmética
$$s=r+kM_d,\qquad k\ge 0.$$
Por eso las implementaciones construyen primero todas las clases CRT y después prueban solo las raíces inducidas por ellas.
La condición modular es necesaria, pero no suficiente. El corte debe ser un corte decimal auténtico, con ambas partes positivas y sin ceros a la izquierda ocultos en el bloque derecho.
Como \(b=s-a\gt 0\), necesitamos \(a\lt s\). Sustituyendo la fórmula de \(a\),
$$\frac{s(s-1)}{M_d}\lt s,$$
lo cual se simplifica a
$$s\lt 10^d.$$
En consecuencia, toda raíz válida satisface
$$2\le s\le \min\!\bigl(\lfloor\sqrt{10^{16}-1}\rfloor,\;10^d-1\bigr).$$
Además, el bloque derecho debe estar en el rango exacto
$$1\le b\lt 10 \quad(d=1),\qquad 10^{d-1}\le b\lt 10^d \quad(d\ge 2).$$
La segunda condición descarta automáticamente casos como \(01\) o \(0017\): el valor numérico es positivo, pero la parte derecha no ocupa realmente \(d\) cifras.
Tomemos \(d=2\). Entonces
$$M_2=10^2-1=99=9\cdot 11.$$
Para \(9\) y \(11\), los únicos residuos locales son \(0\) y \(1\). El CRT produce así cuatro clases globales módulo \(99\):
$$s\equiv 0,\ 1,\ 45,\ 55 \pmod{99}.$$
Como \(s\lt 100\), solo pueden importar los representantes \(45\), \(55\) y \(99\).
Para \(s=45\),
$$a=\frac{45\cdot 44}{99}=20,\qquad b=45-20=25,$$
y por tanto \(45^2=2025=20\mid 25\).
Para \(s=55\),
$$a=\frac{55\cdot 54}{99}=30,\qquad b=55-30=25,$$
y entonces \(55^2=3025=30\mid 25\).
Para \(s=99\),
$$a=\frac{99\cdot 98}{99}=98,\qquad b=1,$$
pero \(b=1\) no tiene dos cifras, así que el corte \(98\mid 01\) queda prohibido. El ejemplo resume perfectamente el método: el CRT genera candidatos modulares y el filtro de cifras elimina los falsos positivos.
La pregunta de Project Euler pide la suma de los números \(n\), no la suma sobre todos los pares exitosos \((n,d)\). Un mismo cuadrado puede cumplir la propiedad para varias longitudes de corte, así que los valores aceptados \(n=s^2\) deben almacenarse como enteros distintos antes de la suma final.
Las implementaciones en C++, Python y Java precomputan las potencias de \(10\), la cota \(\lfloor\sqrt{10^{16}-1}\rfloor\) y una tabla de primos suficiente para factorizar todos los módulos \(10^d-1\) con \(1\le d\le 15\).
Para cada \(d\), la implementación factoriza \(10^d-1\) en potencias primas. Luego parte del módulo trivial \(1\) y va fusionando las dos posibilidades locales \(s\equiv0\) y \(s\equiv1\) módulo cada potencia prima. Tras completar todas las fusiones, queda la lista CRT completa de residuos admisibles \(r\) módulo \(10^d-1\).
Cada clase residual produce una raíz candidata \(s\) dentro del rango permitido. A partir de ella, la implementación calcula \(a=\frac{s(s-1)}{10^d-1}\), luego \(b=s-a\), comprueba que ambas partes sean positivas, comprueba que \(b\) tenga exactamente \(d\) cifras, reconstruye \(n=s^2\) y guarda \(n\) en un conjunto hash. La versión en C++ también incluye pequeñas comprobaciones internas por búsqueda directa para límites de cifras más cortos antes de dar la respuesta para \(10^{16}\).
Sea \(\omega(M_d)\) el número de divisores primos distintos de \(M_d=10^d-1\). Para un \(d\) fijo, la fase CRT genera exactamente \(2^{\omega(M_d)}\) clases residuales, porque cada potencia prima aporta la elección binaria entre \(0\) y \(1\).
En este problema concreto, la cota \(s\lt 10^d\) implica que cada clase residual aporta como mucho una raíz candidata relevante. Así, tras la factorización, el trabajo restante es básicamente un número constante de comprobaciones enteras por residuo CRT. La memoria también es pequeña: una lista de primos, una lista temporal de residuos y el conjunto de cuadrados aceptados. Es muchísimo más eficiente que revisar todas las raíces hasta \(10^8\) y todas las posiciones de corte posibles.
我们要寻找所有小于 \(10^{16}\) 的平方数 \(n\)，使它的十进制表示能够切成一个非空左段和一个非空右段，而且这两段之和正好等于平方根。把 \(n\) 写成 \(n=s^2\) 之后，这个切分可以写为
$$n=a10^d+b,\qquad s=a+b,$$
其中 \(b\) 恰好有 \(d\) 位。题目标题中的例子就是 \(2025=20\mid 25\)，因为 \(20+25=45=\sqrt{2025}\)。目标是把所有这样的平方数相加；如果同一个 \(n\) 对不同的切分长度都成立，也只能计一次。
这个问题和十进制 Kaprekar 数密切相关，但真正高效的做法不是逐个枚举平方数 \(n\)，而是直接研究平方根 \(s\)，并用模运算描述哪些 \(s\) 可能出现。
固定一个切分长度 \(d\)，记
$$M_d=10^d-1.$$
对于这个固定的 \(d\)，问题就变成了：哪些根 \(s\) 能产生合法的十进制切分？
由 \(n=s^2=a10^d+b\) 以及 \(s=a+b\)，把 \(b=s-a\) 代入：
$$s^2=a10^d+(s-a)=s+a(10^d-1).$$
于是立刻得到
$$a=\frac{s(s-1)}{M_d},\qquad b=s-a.$$
这说明一个必要条件是
$$M_d\mid s(s-1).$$
而且一旦 \(a\) 是整数，并且数位条件也满足，那么重构等式自动成立，因为
$$a10^d+b=a(10^d-1)+s=s(s-1)+s=s^2.$$
因此真正的搜索对象不是 \((a,b)\) 这样的切分对，而是满足一个同余条件和若干十进制位数限制的根 \(s\)。
把 \(M_d\) 分解成两两互素的素数幂：
$$M_d=\prod_{i=1}^{t} p_i^{e_i}.$$
由于相邻整数互素，所以 \(\gcd(s,s-1)=1\)。如果某个素数幂 \(p_i^{e_i}\) 整除乘积 \(s(s-1)\)，那么这整个素数幂必然全部落在 \(s\) 或者 \(s-1\) 的其中一个因子里。于是任何合法的根都必须满足
$$s\equiv 0,1 \pmod{p_i^{e_i}},\qquad 1\le i\le t.$$
这一步是整个解法的核心简化。原本看起来要检查所有不超过 \(10^8\) 的平方根，但实际上对 \(10^d-1\) 的每个不同素数幂因子，只需要做一次二选一：模这个素数幂是 \(0\)，还是 \(1\)。
每个素数幂给出两个局部选择，因此固定 \(d\) 之后会得到若干个全局余数类。中国剩余定理把这些局部条件合并成唯一的同余式
$$s\equiv r \pmod{M_d}.$$
于是该切分长度下所有可能的平方根都落在等差数列
$$s=r+kM_d,\qquad k\ge 0$$
之中。代码的做法正是先生成所有 CRT 余数类，再对这些余数类对应的根进行检查。
同余条件只是必要条件，还不够。我们还必须保证这真的是一个合法的十进制切分：左右两段都非空，右段不能通过前导零“伪装”成 \(d\) 位。
因为 \(b=s-a\gt 0\)，所以必须有 \(a\lt s\)。把 \(a\) 的公式代进去：
$$\frac{s(s-1)}{M_d}\lt s,$$
可化为
$$s\lt 10^d.$$
因此每个合法的根都满足
$$2\le s\le \min\!\bigl(\lfloor\sqrt{10^{16}-1}\rfloor,\;10^d-1\bigr).$$
与此同时，右段必须落在精确的位数范围内：
$$1\le b\lt 10 \quad(d=1),\qquad 10^{d-1}\le b\lt 10^d \quad(d\ge 2).$$
第二条条件会自动排除像 \(01\)、\(0017\) 这样的情况。它们作为整数虽然是正数，但并没有真正占据 \(d\) 位，所以不能作为合法右段。
取 \(d=2\)。这时
$$M_2=10^2-1=99=9\cdot 11.$$
对 \(9\) 和 \(11\) 来说，局部余数都只能是 \(0\) 或 \(1\)。因此通过 CRT 可以得到模 \(99\) 的四个全局余数类：
$$s\equiv 0,\ 1,\ 45,\ 55 \pmod{99}.$$
因为 \(s\lt 100\)，真正需要检查的只有代表元 \(45\)、\(55\) 和 \(99\)。
当 \(s=45\) 时，
$$a=\frac{45\cdot 44}{99}=20,\qquad b=45-20=25,$$
于是 \(45^2=2025=20\mid 25\)。
当 \(s=55\) 时，
$$a=\frac{55\cdot 54}{99}=30,\qquad b=55-30=25,$$
于是 \(55^2=3025=30\mid 25\)。
当 \(s=99\) 时，
$$a=\frac{99\cdot 98}{99}=98,\qquad b=1,$$
但 \(b=1\) 不是两位数，所以切分 \(98\mid 01\) 不合法。这个例子完整展示了算法的两层逻辑：CRT 负责生成模意义下的候选，位数检查负责删除错误候选。
题目要求的是数字 \(n\) 的总和，而不是所有成功二元组 \((n,d)\) 的总和。同一个平方数可能对多个切分长度都成立，因此必须先把所有接受的 \(n=s^2\) 作为不同整数存起来，再做最后求和。
C++、Python 和 Java 实现都会先预计算 \(10\) 的幂、上界 \(\lfloor\sqrt{10^{16}-1}\rfloor\)，以及一个足以分解所有 \(1\le d\le 15\) 时 \(10^d-1\) 的素数表。
对于每个 \(d\)，实现先把 \(10^d-1\) 分解成素数幂。然后从模 \(1\) 的平凡同余开始，依次把每个素数幂上的两个局部条件 \(s\equiv0\) 和 \(s\equiv1\) 合并进去。全部合并完成后，就得到了模 \(10^d-1\) 下所有允许的 CRT 余数 \(r\)。
每个余数类都会在允许范围内给出一个候选根 \(s\)。程序据此计算 \(a=\frac{s(s-1)}{10^d-1}\) 和 \(b=s-a\)，检查两部分是否都为正、检查 \(b\) 是否恰好有 \(d\) 位、重构 \(n=s^2\)，然后把 \(n\) 放进哈希集合中。C++ 版本还会先对若干较小位数上限做直接搜索自检，再输出 \(10^{16}\) 的最终结果。
记 \(\omega(M_d)\) 为 \(M_d=10^d-1\) 的不同素因子个数。对固定的 \(d\)，CRT 阶段会精确地产生 \(2^{\omega(M_d)}\) 个余数类，因为每个素数幂都贡献一次 \(0/1\) 的二元选择。
在本题的规模下，约束 \(s\lt 10^d\) 意味着每个余数类最多只会给出一个真正需要检查的根。因此在完成分解之后，剩余工作基本就是对每个 CRT 余数做常数次整数运算和条件判断。内存占用也很小：一个素数表、一个临时余数表，以及保存所有合法平方数的集合。和朴素地枚举所有不超过 \(10^8\) 的平方根并尝试所有切分位置相比，这个复杂度低得多。
Нужно найти все квадраты \(n\lt 10^{16}\), чья десятичная запись разбивается на непустую левую часть и непустую правую часть так, что квадратный корень равен сумме этих частей. Если \(n=s^2\), то разрез записывается как
$$n=a10^d+b,\qquad s=a+b,$$
где число \(b\) имеет ровно \(d\) цифр. Заглавный пример: \(2025=20\mid 25\), потому что \(20+25=45=\sqrt{2025}\). Требуется просуммировать все такие квадраты, причём один и тот же \(n\) нужно учитывать только один раз, даже если он подходит для нескольких длин разреза.
Эта конструкция тесно связана с числами Капрекара в десятичной системе, но эффективное решение удобнее формулировать не через перебор самих квадратов \(n\), а через описание допустимых корней \(s\) средствами модульной арифметики.
Зафиксируем длину разреза \(d\) и обозначим
$$M_d=10^d-1.$$
Для такого фиксированного \(d\) нужно описать все корни \(s\), для которых существует корректное десятичное разбиение.
Из \(n=s^2=a10^d+b\) и \(s=a+b\) подставим \(b=s-a\):
$$s^2=a10^d+(s-a)=s+a(10^d-1).$$
Отсюда следует
$$a=\frac{s(s-1)}{M_d},\qquad b=s-a.$$
Значит, немедленно появляется условие делимости
$$M_d\mid s(s-1).$$
Как только \(a\) оказывается целым и выполнены условия на количество цифр, равенство восстанавливается автоматически, потому что
$$a10^d+b=a(10^d-1)+s=s(s-1)+s=s^2.$$
Итак, искать нужно не пары \((a,b)\) напрямую, а такие корни \(s\), которые удовлетворяют одной конгруэнции и нескольким десятичным ограничениям.
Разложим \(M_d\) на попарно взаимно простые степени простых:
$$M_d=\prod_{i=1}^{t} p_i^{e_i}.$$
Так как соседние целые числа взаимно просты, \(\gcd(s,s-1)=1\). Если \(p_i^{e_i}\) делит произведение \(s(s-1)\), то вся эта степень простого обязана целиком делить либо \(s\), либо \(s-1\). Поэтому любой допустимый корень удовлетворяет условию
$$s\equiv 0,1 \pmod{p_i^{e_i}},\qquad 1\le i\le t.$$
Именно здесь происходит главная экономия. Вместо полного перебора корней до \(10^8\) мы для каждого различного простого степенного множителя числа \(10^d-1\) делаем лишь бинарный выбор: остаток \(0\) или остаток \(1\).
Каждая простая степень даёт две локальные возможности, поэтому для фиксированного \(d\) возникает набор глобальных классов вычетов. Китайская теорема об остатках объединяет эти локальные условия в единственную конгруэнцию
$$s\equiv r \pmod{M_d}.$$
Следовательно, все допустимые корни для данной длины разреза лежат в арифметической прогрессии
$$s=r+kM_d,\qquad k\ge 0.$$
Реализация именно так и устроена: сначала строятся все CRT-классы, а затем проверяются только те корни, которые они задают.
Модульное условие необходимо, но недостаточно. Нужно ещё потребовать, чтобы разрез действительно состоял из двух положительных десятичных блоков, а правая часть не содержала скрытых ведущих нулей.
Так как \(b=s-a\gt 0\), требуется \(a\lt s\). Подставляя формулу для \(a\), получаем
$$\frac{s(s-1)}{M_d}\lt s,$$
откуда следует
$$s\lt 10^d.$$
Значит, любой допустимый корень лежит в диапазоне
$$2\le s\le \min\!\bigl(\lfloor\sqrt{10^{16}-1}\rfloor,\;10^d-1\bigr).$$
Кроме того, правая часть должна лежать в точном диапазоне
$$1\le b\lt 10 \quad(d=1),\qquad 10^{d-1}\le b\lt 10^d \quad(d\ge 2).$$
Вторая граница автоматически исключает записи вроде \(01\) или \(0017\): как числа они положительны, но не занимают ровно \(d\) цифр.
Возьмём \(d=2\). Тогда
$$M_2=10^2-1=99=9\cdot 11.$$
Для \(9\) и \(11\) локально допустимы только остатки \(0\) и \(1\). Поэтому CRT даёт четыре глобальных класса по модулю \(99\):
$$s\equiv 0,\ 1,\ 45,\ 55 \pmod{99}.$$
Так как \(s\lt 100\), реально нужно проверить только представителей \(45\), \(55\) и \(99\).
Для \(s=45\)
$$a=\frac{45\cdot 44}{99}=20,\qquad b=45-20=25,$$
и потому \(45^2=2025=20\mid 25\).
Для \(s=55\)
$$a=\frac{55\cdot 54}{99}=30,\qquad b=55-30=25,$$
и, следовательно, \(55^2=3025=30\mid 25\).
Для \(s=99\)
$$a=\frac{99\cdot 98}{99}=98,\qquad b=1,$$
но \(b=1\) не является двузначным числом, поэтому разрез \(98\mid 01\) запрещён. Этот пример точно показывает, как CRT порождает кандидаты, а проверка числа цифр удаляет ложные срабатывания.
В задаче требуется сумма чисел \(n\), а не сумма по всем удачным парам \((n,d)\). Один и тот же квадрат может удовлетворять условию для нескольких длин разреза. Поэтому подходящие значения \(n=s^2\) нужно сначала сохранить как множество различных целых чисел, и только потом суммировать.
Реализации на C++, Python и Java заранее строят степени \(10\), верхнюю границу \(\lfloor\sqrt{10^{16}-1}\rfloor\) и таблицу простых чисел, достаточную для факторизации всех модулей \(10^d-1\) при \(1\le d\le 15\).
Для каждого \(d\) число \(10^d-1\) раскладывается на степени простых. Затем, начиная с тривиального модуля \(1\), программа последовательно сливает две локальные возможности \(s\equiv0\) и \(s\equiv1\) по модулю каждой простой степени. После всех слияний получается полный список допустимых CRT-остатков \(r\) по модулю \(10^d-1\).
Каждый класс вычетов задаёт кандидатный корень \(s\) в разрешённом диапазоне. По нему вычисляются \(a=\frac{s(s-1)}{10^d-1}\) и \(b=s-a\), проверяется положительность обеих частей, точное число цифр у \(b\), выполняется восстановление \(n=s^2\), после чего \(n\) помещается в хеш-множество. Версия на C++ дополнительно содержит небольшие самопроверки прямым перебором для меньших пределов числа цифр, прежде чем печатать ответ для \(10^{16}\).
Обозначим через \(\omega(M_d)\) число различных простых делителей числа \(M_d=10^d-1\). Для фиксированного \(d\) CRT-этап создаёт ровно \(2^{\omega(M_d)}\) классов вычетов, потому что каждая простая степень даёт бинарный выбор между остатками \(0\) и \(1\).
В этой задаче ограничение \(s\lt 10^d\) означает, что каждый такой класс даёт не более одного действительно релевантного корня. Поэтому после факторизации вся оставшаяся работа сводится почти к постоянному числу целочисленных проверок на один CRT-класс. Память тоже требуется небольшая: список простых, временный список вычетов и множество подходящих квадратов. Это несравнимо дешевле наивного перебора всех корней до \(10^8\) со всеми возможными позициями разреза.
نبحث عن جميع الأعداد المربعة \(n\lt 10^{16}\) التي يمكن قطع كتابتها العشرية إلى جزء أيسر غير فارغ وجزء أيمن غير فارغ بحيث يكون الجذر التربيعي مساويًا لمجموع الجزأين. إذا كتبنا \(n=s^2\) فإن القطع يأخذ الصورة
$$n=a10^d+b,\qquad s=a+b,$$
حيث يملك \(b\) بالضبط \(d\) رقمًا. المثال الذي يحمل اسم المسألة هو \(2025=20\mid 25\)، لأن \(20+25=45=\sqrt{2025}\). المطلوب هو جمع كل هذه المربعات مع حذف التكرار إذا كان العدد نفسه ينجح لأكثر من طول قطع واحد.
هذا يرتبط ارتباطًا مباشرًا بأعداد كابريكار في النظام العشري، لكن الطريقة الفعالة هنا لا تفحص المربعات \(n\) نفسها واحدًا واحدًا، بل تعمل مباشرة على الجذر \(s\) وتصف القيم الممكنة له بواسطة الحسابيات بترديد.
نثبت طول القطع \(d\) ونعرّف
$$M_d=10^d-1.$$
وعندئذٍ تصبح المسألة: ما هي الجذور \(s\) التي تسمح بوجود هذا القطع العشري الصحيح؟
لدينا \(n=s^2=a10^d+b\) و\(s=a+b\). إذا عوّضنا \(b=s-a\) نحصل على
$$s^2=a10^d+(s-a)=s+a(10^d-1).$$
ومن ثم
$$a=\frac{s(s-1)}{M_d},\qquad b=s-a.$$
إذًا الشرط الأساسي هو
$$M_d\mid s(s-1).$$
وحين تكون \(a\) عددًا صحيحًا وتتحقق شروط عدد الأرقام، فإن إعادة البناء تصبح تلقائية، لأن
$$a10^d+b=a(10^d-1)+s=s(s-1)+s=s^2.$$
لذلك فضاء البحث الحقيقي ليس جميع الأزواج \((a,b)\)، بل الجذور \(s\) التي تحقق تطابقًا واحدًا وبعض القيود الرقمية.
نحلل \(M_d\) إلى قوى أولية متمايزة ومتباينة أوليًا فيما بينها:
$$M_d=\prod_{i=1}^{t} p_i^{e_i}.$$
وبما أن عددين متتاليين متباينان أوليًا، فإن \(\gcd(s,s-1)=1\). فإذا كانت القوة الأولية \(p_i^{e_i}\) تقسم حاصل الضرب \(s(s-1)\)، فلا بد أن تقع هذه القوة كاملة في أحد العاملين \(s\) أو \(s-1\). لذلك كل جذر صالح يحقق
$$s\equiv 0,1 \pmod{p_i^{e_i}},\qquad 1\le i\le t.$$
وهذه هي الخطوة الحاسمة في التبسيط. بدلًا من تجربة كل الجذور حتى \(10^8\)، نصبح أمام اختيار ثنائي فقط لكل عامل من نوع قوة أولية يظهر في \(10^d-1\): هل الباقي \(0\) أم \(1\)؟
كل قوة أولية تعطي احتمالين محليين، ولذلك يظهر عند تثبيت \(d\) عدد من فئات البواقي العالمية. مبرهنة البواقي الصينية تجمع هذه الاختيارات في تطابق وحيد
$$s\equiv r \pmod{M_d}.$$
وبالتالي فإن كل الجذور المقبولة لهذا الطول من القطع تقع في متتالية حسابية من الشكل
$$s=r+kM_d,\qquad k\ge 0.$$
ولهذا تبني التطبيقات أولًا جميع فئات CRT ثم تفحص فقط الجذور الناتجة عنها.
شرط التطابق ضروري لكنه غير كافٍ. يجب أيضًا أن يكون القطع قطعًا عشريًا حقيقيًا، وأن يكون الجزآن موجبين، وألا يحتوي الجزء الأيمن على أصفار بادئة مخفية.
بما أن \(b=s-a\gt 0\)، فلا بد من \(a\lt s\). وباستخدام صيغة \(a\) نحصل على
$$\frac{s(s-1)}{M_d}\lt s,$$
ومنها
$$s\lt 10^d.$$
إذن كل جذر صالح يحقق
$$2\le s\le \min\!\bigl(\lfloor\sqrt{10^{16}-1}\rfloor,\;10^d-1\bigr).$$
كما أن الجزء الأيمن يجب أن يقع في المجال الرقمي الدقيق
$$1\le b\lt 10 \quad(d=1),\qquad 10^{d-1}\le b\lt 10^d \quad(d\ge 2).$$
والشرط الثاني هو الذي يستبعد كتابات مثل \(01\) أو \(0017\): قيمتها العددية موجبة، لكنها لا تشغل فعلًا \(d\) خانات.
خذ \(d=2\). عندها
$$M_2=10^2-1=99=9\cdot 11.$$
وبالنسبة إلى \(9\) و\(11\)، فالبواقي المحلية الممكنة هي فقط \(0\) و\(1\). لذلك يعطي CRT أربع فئات عالمية بترديد \(99\):
$$s\equiv 0,\ 1,\ 45,\ 55 \pmod{99}.$$
ولأن \(s\lt 100\)، فإن القيم الممثلة المهمة هي \(45\) و\(55\) و\(99\) فقط.
إذا كان \(s=45\)، فإن
$$a=\frac{45\cdot 44}{99}=20,\qquad b=45-20=25,$$
ومن ثم \(45^2=2025=20\mid 25\).
وإذا كان \(s=55\)، فإن
$$a=\frac{55\cdot 54}{99}=30,\qquad b=55-30=25,$$
ولذلك \(55^2=3025=30\mid 25\).
أما إذا كان \(s=99\)، فنحصل على
$$a=\frac{99\cdot 98}{99}=98,\qquad b=1,$$
لكن \(b=1\) ليس عددًا ذا رقمين، ولذلك يكون القطع \(98\mid 01\) غير مقبول. هذا المثال يوضح الفكرة كاملة: CRT يولد المرشحين على مستوى البواقي، ثم تأتي شروط عدد الخانات لتصفية النتائج الكاذبة.
السؤال يطلب مجموع القيم \(n\)، لا مجموع الأزواج الناجحة \((n,d)\). وقد يحقق مربع واحد الخاصية نفسها لأكثر من طول قطع واحد. لذلك لا بد من تخزين القيم المقبولة \(n=s^2\) كعناصر مميزة في مجموعة قبل إجراء الجمع النهائي.
تقوم تطبيقات C++ وPython وJava بحساب قوى العدد \(10\) مسبقًا، وكذلك الحد الأعلى \(\lfloor\sqrt{10^{16}-1}\rfloor\)، وجدول من الأعداد الأولية يكفي لتحليل جميع القيم \(10^d-1\) عندما يكون \(1\le d\le 15\).
لكل قيمة \(d\)، تقوم الشفرة بتحليل \(10^d-1\) إلى قوى أولية. ثم تبدأ من التطابق التافه بترديد \(1\)، وتدمج بالتتابع الاحتمالين المحليين \(s\equiv0\) و\(s\equiv1\) بترديد كل قوة أولية. وبعد اكتمال جميع عمليات الدمج نحصل على القائمة الكاملة لبواقي CRT المسموح بها \(r\) بترديد \(10^d-1\).
كل فئة باقٍ تعطي جذرًا مرشحًا \(s\) داخل المجال المسموح. بعد ذلك تحسب الشفرة \(a=\frac{s(s-1)}{10^d-1}\) ثم \(b=s-a\)، وتتحقق من كون الجزأين موجبين، ومن أن \(b\) يملك بالضبط \(d\) خانات، ثم تعيد بناء \(n=s^2\) وتضيف \(n\) إلى مجموعة تجزئة. كما تحتوي نسخة C++ على اختبارات تحقق مباشرة صغيرة لحدود أقل قبل إخراج جواب \(10^{16}\).
لنرمز بـ \(\omega(M_d)\) إلى عدد القواسم الأولية المميزة للعدد \(M_d=10^d-1\). عند تثبيت \(d\)، تنتج مرحلة CRT عددًا مقداره \(2^{\omega(M_d)}\) من فئات البواقي، لأن كل قوة أولية تضيف اختيارًا ثنائيًا بين \(0\) و\(1\).
وفي حجم هذه المسألة بالذات، فإن القيد \(s\lt 10^d\) يعني أن كل فئة باقٍ تعطي في أقصى الأحوال جذرًا واحدًا ذا صلة. لذلك، بعد التحليل إلى عوامل، يصبح ما تبقى تقريبًا عددًا ثابتًا من الفحوص الصحيحة لكل باقٍ من بواقي CRT. كما أن الذاكرة المطلوبة صغيرة: قائمة أولية، وقائمة مؤقتة للبواقي، ومجموعة المربعات المقبولة. وهذا أصغر بكثير من فحص كل الجذور حتى \(10^8\) مع كل مواضع القطع الممكنة.