The problem asks for the unique positive integer \(n\) whose square has the decimal form 1_2_3_4_5_6_7_8_9_0, where each underscore stands for an arbitrary digit. In other words, the units digit of \(n^2\) must be \(0\), the hundreds digit must be \(9\), the ten-thousands digit must be \(8\), and so on up to the leading digit \(1\).
A brute-force scan over all nearby integers would still be far larger than necessary. The implementations therefore combine three precise ideas: a tight square-root interval, a modular restriction on the last two digits of the root, and a purely arithmetic verifier that peels the square two digits at a time.
The decimal mask already tells us almost everything. Once we translate the pattern into inequalities and congruences, the search becomes a small filtered sweep rather than an open-ended trial.
If the hidden digits are all minimized to \(0\), the square is at least
$$L=1020304050607080900.$$
If the hidden digits are all maximized to \(9\), the square is at most
$$U=1929394959697989990.$$
Therefore every valid root must satisfy
$$\left\lceil \sqrt{L} \right\rceil \le n \le \left\lfloor \sqrt{U} \right\rfloor,$$
that is,
$$1010101011 \le n \le 1389026623.$$
This already collapses the problem to a finite interval of plausible roots.
The pattern ends in \(0\), so \(n^2\) is divisible by \(10\). A square can end in \(0\) only when the root itself is divisible by \(10\), so we may write
$$n=10m.$$
Then
$$m^2=\frac{n^2}{100}$$
must end in \(9\), because removing the final two zeros from a valid square exposes the fixed digit \(9\). Hence
$$m^2 \equiv 9 \pmod{10}.$$
The only residues whose squares are \(9\) modulo \(10\) are \(3\) and \(7\), so
$$m \equiv 3 \text{ or } 7 \pmod{10},$$
which is equivalent to
$$n \equiv 30 \text{ or } 70 \pmod{100}.$$
This is exactly the filter used by the implementations: among multiples of \(10\), only those ending in \(30\) or \(70\) can possibly work.
It is useful to see the last-digit argument concretely. Among numbers ending in \(10,30,50,70,90\), the corresponding squares satisfy
$$10^2 \equiv 100,\quad 30^2 \equiv 900,\quad 50^2 \equiv 500,\quad 70^2 \equiv 900,\quad 90^2 \equiv 100 \pmod{1000}.$$
A valid square must end in \(900\), because its last three digits are forced to be 9_0 with the middle digit hidden. The congruence table shows that only the endings \(30\) and \(70\) survive.
After the residue filter, the remaining question is whether a candidate square matches every forced digit. The code does not build strings or use pattern matching. Instead, it checks the required digits numerically.
For a candidate square \(s=n^2\), validity is equivalent to the system
$$s \equiv 0 \pmod{10},$$
and, for \(k=1,2,\dots,9\),
$$\left\lfloor \frac{s}{10^{2k}} \right\rfloor \bmod 10 = 10-k.$$
These equations say exactly that the digits in positions \(10^0,10^2,10^4,\dots,10^{18}\) are \(0,9,8,\dots,1\). The implementations realize this by first checking the units digit, then repeatedly dividing by \(100\). Each division discards one hidden digit together with one already verified fixed digit, so the next fixed digit becomes the new units digit.
If we define
$$s_0=s,\qquad s_{r+1}=\left\lfloor \frac{s_r}{100} \right\rfloor,$$
then a valid square must satisfy
$$s_0 \bmod 10 = 0,\qquad s_r \bmod 10 = 10-r \quad (r=1,\dots,9).$$
This invariant is the heart of the checker.
The interval from \(1010101011\) to \(1389026623\) contains about \(3.79\times 10^8\) integers, but the first divisibility condition lets us step by \(10\), and the residue condition keeps only two endings out of every hundred. That leaves only about \(7.6\times 10^6\) serious candidates, and each candidate needs only a constant number of arithmetic tests. For this problem size, that is entirely practical.
The C++, Python, and Java implementations begin by computing the integer square-root bounds implied by the smallest and largest masked squares. The lower bound is then advanced to a multiple of \(10\), because no valid root can avoid that divisibility condition.
The main loop advances through the interval in steps of \(10\). For each candidate root, the implementation inspects its last two digits and immediately discards anything that is not congruent to \(30\) or \(70\) modulo \(100\). This removes the overwhelming majority of candidates before any square-pattern work is done.
For the surviving candidates, the implementation squares the root and performs the digit test described above. It first verifies the final \(0\), then repeatedly divides the square by \(100\) and checks that the newly exposed units digit is \(9,8,7,\dots,1\) in order. Because the pattern is fixed, the verifier uses only integer arithmetic and a short loop over those nine required digits.
The search stops as soon as a candidate passes the full test. One implementation also includes small checkpoint cases for the digit verifier, confirming that the mask checker accepts the canonical lower template and rejects a nearby incorrect value.
Let
$$I=\left\lfloor \sqrt{U} \right\rfloor-\left\lceil \sqrt{L} \right\rceil+1.$$
A naive scan over all integers in that interval would cost \(O(I)\) candidate generations. The implementations still have linear worst-case behavior in the width of the interval, but with a much smaller constant: they inspect only multiples of \(10\), and among those they fully test only the roots congruent to \(30\) or \(70\) modulo \(100\). So the number of full pattern checks is roughly \(I/50\).
Each pattern check performs a square and then a fixed number of digit inspections, so its cost is \(O(1)\). The overall running time is therefore \(O(I)\) with strong constant-factor pruning, and the memory usage is \(O(1)\) because the algorithm stores only a handful of integers.
Gesucht ist die eindeutige positive ganze Zahl \(n\), deren Quadrat die Dezimalform 1_2_3_4_5_6_7_8_9_0 besitzt. Jeder Unterstrich steht für genau eine beliebige Ziffer. Anders gesagt: Die Einerstelle von \(n^2\) ist \(0\), die Hunderterstelle ist \(9\), die Zehntausenderstelle ist \(8\) und so weiter bis zur führenden \(1\).
Eine rohe Vollsuche über alle benachbarten Zahlen wäre unnötig teuer. Die Implementierungen reduzieren den Suchraum deshalb mit drei präzisen Werkzeugen: engen Wurzelgrenzen, einer Kongruenzbedingung für die Endziffern der Wurzel und einem rein arithmetischen Prüfer, der das Quadrat jeweils um zwei Stellen verkürzt.
Die Maskierung im Quadrat liefert sofort harte Informationen. Sobald man sie als Schranken und Kongruenzen formuliert, bleibt nur noch eine kleine gefilterte Suche übrig.
Wenn alle verdeckten Stellen minimal \(0\) sind, erhält man als kleinstmögliches Quadrat
$$L=1020304050607080900.$$
Wenn alle verdeckten Stellen maximal \(9\) sind, ergibt sich als größtmögliches Quadrat
$$U=1929394959697989990.$$
Jede gültige Wurzel muss also
$$\left\lceil \sqrt{L} \right\rceil \le n \le \left\lfloor \sqrt{U} \right\rfloor$$
erfüllen, also konkret
$$1010101011 \le n \le 1389026623.$$
Damit ist das Problem sofort auf ein endliches und recht enges Intervall begrenzt.
Das gesuchte Quadrat endet auf \(0\). Daher ist \(n^2\) durch \(10\) teilbar, und das ist bei einer Quadratzahl nur möglich, wenn bereits die Wurzel selbst durch \(10\) teilbar ist. Schreibe also
$$n=10m.$$
Dann muss
$$m^2=\frac{n^2}{100}$$
auf \(9\) enden, denn nach dem Entfernen der letzten beiden Nullen wird die feste Ziffer \(9\) sichtbar. Also gilt
$$m^2 \equiv 9 \pmod{10}.$$
Modulo \(10\) haben nur die Restklassen \(3\) und \(7\) ein Quadrat mit Endziffer \(9\). Deshalb
$$m \equiv 3 \text{ oder } 7 \pmod{10},$$
und damit äquivalent
$$n \equiv 30 \text{ oder } 70 \pmod{100}.$$
Genau diese Kongruenz wird im Programm benutzt: Unter allen Vielfachen von \(10\) bleiben nur Kandidaten mit den Endungen \(30\) oder \(70\) übrig.
Die letzte Ziffernklasse lässt sich direkt ausrechnen. Für Zahlen mit den Endungen \(10,30,50,70,90\) gilt
$$10^2 \equiv 100,\quad 30^2 \equiv 900,\quad 50^2 \equiv 500,\quad 70^2 \equiv 900,\quad 90^2 \equiv 100 \pmod{1000}.$$
Ein gültiges Quadrat muss auf \(900\) enden, denn die letzten drei Stellen haben die Form 9_0. Genau deshalb überleben nur \(30\) und \(70\).
Nach der Kongruenzfilterung muss nur noch geprüft werden, ob ein Kandidatenquadrat alle festen Stellen besitzt. Die Implementierungen wandeln das Quadrat nicht in einen String um, sondern testen die Ziffern direkt mit Ganzzahlarithmetik.
Für \(s=n^2\) ist Gültigkeit äquivalent zu
$$s \equiv 0 \pmod{10},$$
und für \(k=1,2,\dots,9\) zu
$$\left\lfloor \frac{s}{10^{2k}} \right\rfloor \bmod 10 = 10-k.$$
Diese Bedingungen sagen exakt, dass die Stellen \(10^0,10^2,10^4,\dots,10^{18}\) die Ziffern \(0,9,8,\dots,1\) tragen. Praktisch wird zuerst die Einerstelle geprüft, dann das Quadrat wiederholt durch \(100\) geteilt. Bei jedem Schritt verschwinden genau eine freie Stelle und eine bereits kontrollierte feste Stelle, sodass die nächste feste Ziffer an die Einerstelle rückt.
Mit
$$s_0=s,\qquad s_{r+1}=\left\lfloor \frac{s_r}{100} \right\rfloor$$
lautet die Invariante
$$s_0 \bmod 10 = 0,\qquad s_r \bmod 10 = 10-r \quad (r=1,\dots,9).$$
Genau das ist der Kern des numerischen Prüfers.
Zwischen \(1010101011\) und \(1389026623\) liegen ungefähr \(3{,}79\times 10^8\) ganze Zahlen. Die Teilbarkeit durch \(10\) erlaubt jedoch Schritte der Größe \(10\), und die Kongruenz \(30\) oder \(70\) modulo \(100\) lässt nur zwei Endungen pro hundert Zahlen zu. Damit bleiben nur ungefähr \(7{,}6\times 10^6\) ernsthafte Kandidaten, und jeder davon wird mit nur wenigen arithmetischen Operationen geprüft.
Die C++-, Python- und Java-Implementierungen bestimmen zuerst die ganzzahligen Wurzelgrenzen, die aus dem kleinsten und größten maskierten Quadrat folgen. Anschließend wird die untere Grenze bis zum nächsten Vielfachen von \(10\) erhöht, weil jede gültige Lösung diese Eigenschaft erfüllen muss.
Die Hauptschleife läuft in Zehnerschritten durch das Intervall. Für jede Wurzel werden die letzten beiden Ziffern betrachtet; alles, was nicht \(30\) oder \(70\) modulo \(100\) ist, wird sofort verworfen. Auf diese Weise wird der Suchraum massiv verkleinert, bevor überhaupt die eigentliche Musterprüfung beginnt.
Für die verbliebenen Kandidaten berechnet die Implementierung das Quadrat und testet es mit der oben beschriebenen Zifferninvariante. Zuerst wird die Schlussziffer \(0\) geprüft. Danach teilt man wiederholt durch \(100\) und verlangt, dass die jeweils neu freigelegte Einerstelle nacheinander \(9,8,7,\dots,1\) ist. Weil das Muster vollständig festliegt, reichen dafür Ganzzahloperationen und eine kurze Schleife.
Die Suche stoppt sofort beim ersten vollständigen Treffer. Eine der Implementierungen enthält außerdem kleine interne Kontrollfälle für den Ziffernprüfer: Eine kanonische positive Vorlage wird akzeptiert, ein naher falscher Wert wird abgelehnt.
Sei
$$I=\left\lfloor \sqrt{U} \right\rfloor-\left\lceil \sqrt{L} \right\rceil+1.$$
Eine naive Suche über alle Zahlen im Intervall hätte linearen Aufwand \(O(I)\). Die Implementierungen behalten diese lineare Grundform, reduzieren aber den konstanten Faktor stark: Es werden nur Vielfache von \(10\) besucht, und vollständig geprüft werden unter ihnen nur die Zahlen mit Rest \(30\) oder \(70\) modulo \(100\). Die Zahl der vollständigen Musterprüfungen liegt daher ungefähr bei \(I/50\).
Jede einzelne Prüfung benötigt ein Quadrat und danach nur eine feste Anzahl von Ziffernvergleichen. Somit kostet ein Test \(O(1)\), die Gesamtlaufzeit ist \(O(I)\) mit sehr günstiger Konstante, und der Speicherbedarf ist \(O(1)\).
Soruda, karesi 1_2_3_4_5_6_7_8_9_0 biçiminde olan tek pozitif tam sayı \(n\) aranır. Buradaki her alt çizgi herhangi bir rakam olabilir. Yani \(n^2\) sayısının birler basamağı \(0\), yüzler basamağı \(9\), on binler basamağı \(8\) ve bu düzen en soldaki \(1\)'e kadar devam etmelidir.
Yakındaki tüm sayıları körlemesine denemek mümkün olsa da gereksiz derecede pahalı olur. Uygulamalar bunun yerine üç net matematiksel daraltma kullanır: kare için keskin alt-üst sınırlar, kökün son iki basamağına ilişkin modüler bir filtre ve kareyi iki basamakta bir soyarak çalışan tamamen sayısal bir doğrulama.
Bu problemde asıl iş, ondalık maskeyi eşitsizlik ve kongruens cümlelerine çevirmektir. Bu yapıldığında geriye açık uçlu bir arama değil, güçlü biçimde filtrelenmiş sonlu bir tarama kalır.
Gizli rakamların hepsi \(0\) seçilirse elde edilebilecek en küçük kare
$$L=1020304050607080900$$
olur. Hepsi \(9\) seçilirse elde edilebilecek en büyük kare ise
$$U=1929394959697989990$$
olur. O halde geçerli her çözüm için
$$\left\lceil \sqrt{L} \right\rceil \le n \le \left\lfloor \sqrt{U} \right\rfloor$$
zorunludur; yani sayısal olarak
$$1010101011 \le n \le 1389026623.$$
Böylece problem daha ilk adımda makul büyüklükte tek bir aralığa iner.
Desen \(0\) ile bittiği için \(n^2\) sayısı \(10\)'a tam bölünür. Bir kare ancak kökü de \(10\)'un katıysa \(0\) ile bitebilir. Bu yüzden
$$n=10m$$
yazılabilir. O zaman
$$m^2=\frac{n^2}{100}$$
sayısının son basamağı \(9\) olmak zorundadır; çünkü geçerli bir kareden sondaki iki sıfırı attığımızda ortaya çıkan sabit rakam \(9\)'dur. Demek ki
$$m^2 \equiv 9 \pmod{10}.$$
\(10\) modunda karesi \(9\) olan tek kalıntılar \(3\) ve \(7\)'dir. Buradan
$$m \equiv 3 \text{ veya } 7 \pmod{10}$$
ve eşdeğer olarak
$$n \equiv 30 \text{ veya } 70 \pmod{100}$$
çıkar. Kodun son iki basamak filtresi tam olarak bu matematiksel zorunluluğu uygular.
Bu sonucun neden doğru olduğunu küçük bir tabloyla görmek kolaydır. Sonu \(10,30,50,70,90\) ile biten sayıların kareleri için
$$10^2 \equiv 100,\quad 30^2 \equiv 900,\quad 50^2 \equiv 500,\quad 70^2 \equiv 900,\quad 90^2 \equiv 100 \pmod{1000}$$
olur. Aradığımız kare son üç basamakta mutlaka 9_0 yapısına sahip olduğu için yalnızca \(900\) ile biten durumlar yaşayabilir. Bu da yalnızca \(30\) ve \(70\) sonlarını bırakır.
Modüler elemeden sonra geriye tek bir iş kalır: aday karenin bütün sabit rakamları gerçekten doğru mu? Uygulamalar bunu metne çevirerek değil, doğrudan tamsayı aritmetiğiyle kontrol eder.
\(s=n^2\) olsun. Geçerlilik şu koşullara denktir:
$$s \equiv 0 \pmod{10},$$
ve \(k=1,2,\dots,9\) için
$$\left\lfloor \frac{s}{10^{2k}} \right\rfloor \bmod 10 = 10-k.$$
Bu eşitlikler, \(10^0,10^2,10^4,\dots,10^{18}\) konumlarındaki rakamların sırasıyla \(0,9,8,\dots,1\) olduğunu söyler. Kodun yaptığı tam olarak budur: önce birler basamağındaki \(0\)'ı denetler, sonra kareyi tekrar tekrar \(100\)'e böler. Her bölme, bir gizli rakamı ve daha önce doğrulanmış bir sabit rakamı birlikte atar; böylece sıradaki sabit rakam yeni birler basamağına gelir.
Eğer
$$s_0=s,\qquad s_{r+1}=\left\lfloor \frac{s_r}{100} \right\rfloor$$
olarak tanımlarsak geçerli bir kare için
$$s_0 \bmod 10 = 0,\qquad s_r \bmod 10 = 10-r \quad (r=1,\dots,9)$$
olmalıdır. Sayısal doğrulayıcının temel değişmezi budur.
\(1010101011\) ile \(1389026623\) arasında yaklaşık \(3.79\times 10^8\) tam sayı vardır. Fakat ilk şart sayesinde yalnızca \(10\)'ar adımlarla ilerlemek yeterlidir; ikinci şart ise her yüz sayının sadece iki sonunu korur. Böylece ciddi biçimde test edilen aday sayısı yaklaşık \(7.6\times 10^6\) düzeyine iner. Her aday için de sabit sayıda aritmetik işlem yeterlidir.
C++, Python ve Java uygulamaları önce maskenin izin verdiği en küçük ve en büyük karelerden tam sayı karekök sınırlarını çıkarır. Alt sınır daha sonra \(10\)'un bir sonraki katına hizalanır; çünkü geçerli kökün bundan kaçması mümkün değildir.
Ana döngü aralık boyunca \(10\)'ar artar. Her aday için son iki basamak okunur ve \(100\) modunda \(30\) ya da \(70\) olmayan her değer anında elenir. Böylece kareyi ayrıntılı inceleme aşamasına ancak çok küçük bir alt küme ulaşır.
Geriye kalan adaylar karesi alınarak kontrol edilir. Önce son basamağın \(0\) olduğu doğrulanır. Daha sonra sayı art arda \(100\)'e bölünür ve her adımda ortaya çıkan yeni birler basamağının sırayla \(9,8,7,\dots,1\) olması istenir. Desen sabit olduğu için bu işlemin tamamı tamsayı aritmetiği ve kısa bir döngüyle yapılır.
İlk tam eşleşme bulunduğunda arama sonlanır. Ayrıca uygulamalardan biri, bu rakam doğrulayıcısının doğru çalıştığını göstermek için küçük olumlu ve olumsuz kontrol örnekleri de içerir.
$$I=\left\lfloor \sqrt{U} \right\rfloor-\left\lceil \sqrt{L} \right\rceil+1$$
olsun. Tüm aralığı ham biçimde taramak \(O(I)\) zaman gerektirir. Buradaki uygulamalar yine doğrusal ölçeklenir, fakat sabit çarpanı sert biçimde küçültür: yalnızca \(10\)'un katları ziyaret edilir ve tam desen kontrolü bunların içinde sadece \(30\) veya \(70\) ile bitenlere uygulanır. Bu yüzden tam doğrulama sayısı yaklaşık \(I/50\) kadardır.
Her doğrulama bir kare alma işlemi ve ardından sabit sayıda rakam karşılaştırmasından oluşur; yani aday başına maliyet \(O(1)\)'dir. Toplam süre \(O(I)\), bellek kullanımı ise yalnızca birkaç tamsayı tutulduğu için \(O(1)\)'dir.
Se busca el único entero positivo \(n\) cuyo cuadrado tiene la forma decimal 1_2_3_4_5_6_7_8_9_0. Cada guion bajo representa un dígito cualquiera. Dicho de otro modo, en \(n^2\) están fijados el dígito de las unidades, el de las centenas, el de las decenas de millar, y así sucesivamente, con la secuencia \(0,9,8,\dots,1\) leída desde la derecha.
Probar todos los enteros cercanos sería innecesariamente caro. Las implementaciones reducen el problema con tres herramientas concretas: un intervalo muy ajustado para la raíz cuadrada, una restricción modular sobre las dos últimas cifras de la raíz y un verificador aritmético que comprueba el patrón quitando dos cifras en cada paso.
La propia máscara decimal contiene casi toda la información. Al traducirla a desigualdades y congruencias, la búsqueda queda convertida en un barrido finito muy filtrado.
Si todos los dígitos ocultos son \(0\), el cuadrado más pequeño posible es
$$L=1020304050607080900.$$
Si todos son \(9\), el cuadrado más grande posible es
$$U=1929394959697989990.$$
Por tanto, toda solución debe cumplir
$$\left\lceil \sqrt{L} \right\rceil \le n \le \left\lfloor \sqrt{U} \right\rfloor,$$
es decir,
$$1010101011 \le n \le 1389026623.$$
Con esto el problema ya queda restringido a un intervalo concreto y manejable.
El patrón termina en \(0\), así que \(n^2\) es divisible por \(10\). Una potencia cuadrada solo puede terminar en \(0\) si la raíz es múltiplo de \(10\), de modo que escribimos
$$n=10m.$$
Entonces
$$m^2=\frac{n^2}{100}$$
debe terminar en \(9\), porque al eliminar los dos ceros finales del cuadrado válido aparece la cifra fija \(9\). Por lo tanto,
$$m^2 \equiv 9 \pmod{10}.$$
Las únicas clases residuales cuyo cuadrado vale \(9\) módulo \(10\) son \(3\) y \(7\). En consecuencia,
$$m \equiv 3 \text{ o } 7 \pmod{10},$$
y eso equivale a
$$n \equiv 30 \text{ o } 70 \pmod{100}.$$
Ese es exactamente el filtro que usa el código antes de realizar la comprobación completa del patrón.
Conviene ver esta restricción con un ejemplo pequeño. Para números que terminan en \(10,30,50,70,90\), se tiene
$$10^2 \equiv 100,\quad 30^2 \equiv 900,\quad 50^2 \equiv 500,\quad 70^2 \equiv 900,\quad 90^2 \equiv 100 \pmod{1000}.$$
Un cuadrado válido debe terminar en \(900\), porque sus tres últimas posiciones tienen la forma 9_0. La tabla muestra que solo sobreviven los finales \(30\) y \(70\).
Después del filtrado modular, queda decidir si el cuadrado de un candidato coincide con todas las cifras obligatorias. Las implementaciones no convierten el número a texto; lo comprueban directamente con divisiones enteras.
Si \(s=n^2\), entonces la validez equivale a
$$s \equiv 0 \pmod{10},$$
y para \(k=1,2,\dots,9\),
$$\left\lfloor \frac{s}{10^{2k}} \right\rfloor \bmod 10 = 10-k.$$
Estas igualdades dicen que las cifras situadas en \(10^0,10^2,10^4,\dots,10^{18}\) son exactamente \(0,9,8,\dots,1\). La implementación lo aprovecha así: primero verifica la cifra final \(0\); después divide repetidamente entre \(100\). Cada división elimina una cifra libre y una cifra fija ya verificada, de modo que la siguiente cifra fija pasa a ser la nueva cifra de las unidades.
Definiendo
$$s_0=s,\qquad s_{r+1}=\left\lfloor \frac{s_r}{100} \right\rfloor,$$
el invariante buscado es
$$s_0 \bmod 10 = 0,\qquad s_r \bmod 10 = 10-r \quad (r=1,\dots,9).$$
Esa es la idea central del verificador numérico.
Entre \(1010101011\) y \(1389026623\) hay aproximadamente \(3.79\times 10^8\) enteros. Sin embargo, la divisibilidad por \(10\) permite avanzar de diez en diez, y la congruencia \(30\) o \(70\) módulo \(100\) deja solo dos terminaciones posibles por cada cien números. Al final solo quedan unos \(7.6\times 10^6\) candidatos serios, y cada uno requiere un número constante de operaciones.
Las implementaciones en C++, Python y Java calculan primero los límites enteros de la raíz cuadrada a partir del menor y del mayor cuadrado compatibles con la máscara. Después ajustan el extremo inferior al siguiente múltiplo de \(10\), porque cualquier solución válida debe cumplir esa divisibilidad.
El bucle principal recorre el intervalo en pasos de \(10\). Para cada candidato, se examinan sus dos últimas cifras y se descarta inmediatamente todo número que no sea congruente con \(30\) o \(70\) módulo \(100\). Así, la prueba completa del patrón solo se ejecuta sobre una fracción muy pequeña del intervalo total.
Para los candidatos que sobreviven, la implementación calcula el cuadrado y aplica la prueba por divisiones sucesivas entre \(100\). Primero confirma el \(0\) final. Luego exige que las nuevas cifras de las unidades sean \(9,8,7,\dots,1\) en ese orden. Como el patrón está completamente fijado, basta una pequeña rutina de aritmética entera.
La búsqueda se detiene en cuanto aparece el primer candidato válido. Además, una de las implementaciones incluye pequeñas comprobaciones internas para asegurar que el verificador acepta un caso positivo canónico y rechaza un caso cercano incorrecto.
Sea
$$I=\left\lfloor \sqrt{U} \right\rfloor-\left\lceil \sqrt{L} \right\rceil+1.$$
Un barrido ingenuo de todos los enteros tendría coste \(O(I)\). Las implementaciones conservan esa dependencia lineal respecto al ancho del intervalo, pero reducen mucho la constante: solo recorren múltiplos de \(10\), y dentro de ellos solo realizan la prueba completa sobre los que terminan en \(30\) o \(70\). Por ello, el número de verificaciones completas es aproximadamente \(I/50\).
Cada verificación necesita un cuadrado y después una cantidad fija de inspecciones de dígitos, así que cuesta \(O(1)\). El tiempo total es \(O(I)\) con un factor constante pequeño y el uso de memoria es \(O(1)\).
题目要求找到唯一的正整数 \(n\)，使得 \(n^2\) 的十进制表示满足 1_2_3_4_5_6_7_8_9_0 这个掩码，其中每个下划线都代表一个任意数字。换句话说，从右往左看，个位必须是 \(0\)，百位必须是 \(9\)，万位必须是 \(8\)，再往上依次固定，直到最高位是 \(1\)。
如果直接把附近所有整数逐个平方再检查，当然也能做，但浪费很大。实现真正利用的是三层筛选：先由掩码得到严格的平方上下界，再由末尾数字得到根的同余条件，最后用纯整数运算逐步剥离两位数字，验证所有被固定的位置。
这个题的关键不在于复杂公式，而在于把十进制模式翻译成可以直接计算的不等式和模条件。一旦翻译完成，搜索空间会缩小到一个完全可控的规模。
如果所有隐藏位都取最小值 \(0\)，那么满足掩码的最小平方就是
$$L=1020304050607080900.$$
如果所有隐藏位都取最大值 \(9\)，那么满足掩码的最大平方就是
$$U=1929394959697989990.$$
因此任何可行解都必须满足
$$\left\lceil \sqrt{L} \right\rceil \le n \le \left\lfloor \sqrt{U} \right\rfloor,$$
也就是
$$1010101011 \le n \le 1389026623.$$
这样一来，问题立刻从“无限猜测”变成“有限区间内搜索”。
因为目标平方的最后一位是 \(0\)，所以 \(n^2\) 能被 \(10\) 整除。一个平方数若以 \(0\) 结尾，它的平方根本身也必须是 \(10\) 的倍数，因此可以写成
$$n=10m.$$
于是
$$m^2=\frac{n^2}{100}$$
的最后一位必须是 \(9\)。这是因为从合法的 \(n^2\) 中去掉最后两个零之后，露出来的固定数字正好就是 \(9\)。因此有
$$m^2 \equiv 9 \pmod{10}.$$
模 \(10\) 下只有 \(3\) 和 \(7\) 的平方会得到 \(9\)，所以
$$m \equiv 3 \text{ 或 } 7 \pmod{10},$$
等价地说，
$$n \equiv 30 \text{ 或 } 70 \pmod{100}.$$
这正是实现中最重要的末尾筛选条件：在所有 \(10\) 的倍数里，只有末两位是 \(30\) 或 \(70\) 的候选者还值得继续检查。
把这个结论算一遍会更直观。对末尾分别是 \(10,30,50,70,90\) 的数，有
$$10^2 \equiv 100,\quad 30^2 \equiv 900,\quad 50^2 \equiv 500,\quad 70^2 \equiv 900,\quad 90^2 \equiv 100 \pmod{1000}.$$
目标平方的最后三位必须是 9_0 的形式，所以真正允许的末三位只能是 \(900\)。从这个小表里立刻能看出，只有 \(30\) 和 \(70\) 两种结尾会留下来。
经过同余筛选以后，剩下的问题是：某个候选平方是否真的在所有固定位置上都匹配掩码？这里完全没有必要把数字转成字符串。实现直接利用整数除法和取模来做验证。
设 \(s=n^2\)。那么合法性等价于
$$s \equiv 0 \pmod{10},$$
并且对于 \(k=1,2,\dots,9\)，都有
$$\left\lfloor \frac{s}{10^{2k}} \right\rfloor \bmod 10 = 10-k.$$
这组条件准确表达了一个事实：在 \(10^0,10^2,10^4,\dots,10^{18}\) 这些位置上的数字，必须依次是 \(0,9,8,\dots,1\)。实现中的检查方式与这个公式完全一致。它先确认个位是 \(0\)，然后不断把平方除以 \(100\)。每除一次，就同时去掉一个已经验证过的固定数字和它旁边那个原本任意的隐藏数字，于是下一个固定数字就被移到了个位，正好可以继续检查。
如果定义
$$s_0=s,\qquad s_{r+1}=\left\lfloor \frac{s_r}{100} \right\rfloor,$$
那么合法平方必须满足
$$s_0 \bmod 10 = 0,\qquad s_r \bmod 10 = 10-r \quad (r=1,\dots,9).$$
这个不变量就是数值检查器的核心。
从 \(1010101011\) 到 \(1389026623\) 一共有大约 \(3.79\times 10^8\) 个整数，看上去不少。但第一个条件让我们只需要按 \(10\) 为步长前进，第二个条件又让每 \(100\) 个整数里只有两个末尾会继续保留。这样真正进入完整掩码验证的候选者只剩大约 \(7.6\times 10^6\) 个，而每个候选者只做常数次整数运算，所以总体规模完全可接受。
C++、Python 和 Java 实现都会先根据最小可能平方与最大可能平方计算整数平方根边界。随后把下界调整到下一个 \(10\) 的倍数，因为任何合法根都必须满足这一点。
主循环以 \(10\) 为步长扫描整个区间。对每个候选根，代码先看末两位；如果它不是模 \(100\) 意义下的 \(30\) 或 \(70\)，就立刻丢弃。这样，绝大多数数字在真正平方之前就已经被筛掉了。
对通过末尾筛选的候选者，实现先计算平方，然后执行逐步除以 \(100\) 的验证过程。先检查最后一位 \(0\)，再要求新露出的个位数字依次是 \(9,8,7,\dots,1\)。由于目标模式完全固定，所以整个过程只依赖整数乘法、整除和取模，不需要字符串、正则表达式或额外数据结构。
一旦发现第一个完全匹配的候选者，搜索就结束。其中一个实现还附带了很小的自检样例，用来确认数值验证器能接受正确模板并拒绝接近但错误的数字。
记
$$I=\left\lfloor \sqrt{U} \right\rfloor-\left\lceil \sqrt{L} \right\rceil+1.$$
如果朴素地把区间中的每个整数都试一遍，时间复杂度是 \(O(I)\)。这里的实现从渐近阶上看仍然是线性的，但常数因子被大幅削减：只访问 \(10\) 的倍数，而其中只有模 \(100\) 下为 \(30\) 或 \(70\) 的数才会进入完整模式检查。因此完整验证的次数大约只有 \(I/50\)。
每次验证都只需要一次平方和固定次数的数字检查，所以单个候选者的成本是 \(O(1)\)。总时间复杂度是 \(O(I)\)，空间复杂度是 \(O(1)\)。
Нужно найти единственное положительное целое число \(n\), квадрат которого имеет десятичный шаблон 1_2_3_4_5_6_7_8_9_0. Каждый символ подчеркивания обозначает произвольную цифру. Иначе говоря, в числе \(n^2\) заранее фиксированы цифры на позициях единиц, сотен, десятков тысяч и так далее: справа налево это последовательность \(0,9,8,\dots,1\).
Наивный перебор всех близких целых чисел дал бы слишком большой лишний объём работы. Реальные реализации опираются на три точных наблюдения: жёсткие границы для квадратного корня, модульное ограничение на последние две цифры корня и арифметическую проверку, которая снимает квадрат по две цифры за шаг.
Сама маска числа уже задаёт почти всю структуру задачи. Если перевести её в язык неравенств и сравнений по модулю, остаётся уже не грубый перебор, а очень узкий отфильтрованный просмотр.
Если все скрытые цифры равны \(0\), то минимально возможный квадрат равен
$$L=1020304050607080900.$$
Если все скрытые цифры равны \(9\), то максимально возможный квадрат равен
$$U=1929394959697989990.$$
Следовательно, любой допустимый корень обязан удовлетворять
$$\left\lceil \sqrt{L} \right\rceil \le n \le \left\lfloor \sqrt{U} \right\rfloor,$$
то есть
$$1010101011 \le n \le 1389026623.$$
После этого задача сразу сводится к конечному и довольно узкому интервалу.
Искомый квадрат оканчивается на \(0\), значит, \(n^2\) делится на \(10\). Квадрат может оканчиваться на \(0\) только тогда, когда и сам корень делится на \(10\), поэтому запишем
$$n=10m.$$
Тогда
$$m^2=\frac{n^2}{100}$$
должен оканчиваться на \(9\), потому что после удаления двух последних нулей из допустимого квадрата открывается фиксированная цифра \(9\). Значит,
$$m^2 \equiv 9 \pmod{10}.$$
По модулю \(10\) только остатки \(3\) и \(7\) имеют квадрат, оканчивающийся на \(9\). Отсюда
$$m \equiv 3 \text{ или } 7 \pmod{10},$$
а значит, эквивалентно
$$n \equiv 30 \text{ или } 70 \pmod{100}.$$
Именно это условие и используется как главный фильтр по последним двум цифрам.
Удобно увидеть это на маленькой таблице. Для чисел, оканчивающихся на \(10,30,50,70,90\), имеем
$$10^2 \equiv 100,\quad 30^2 \equiv 900,\quad 50^2 \equiv 500,\quad 70^2 \equiv 900,\quad 90^2 \equiv 100 \pmod{1000}.$$
Допустимый квадрат обязан оканчиваться на \(900\), потому что его последние три позиции имеют вид 9_0. Из таблицы сразу видно, что проходят только окончания \(30\) и \(70\).
После модульного отсева остаётся проверить, совпадают ли все фиксированные цифры у квадрата кандидата. Реализации делают это без строк и шаблонов, только средствами целочисленной арифметики.
Пусть \(s=n^2\). Тогда допустимость эквивалентна условиям
$$s \equiv 0 \pmod{10},$$
а для \(k=1,2,\dots,9\)
$$\left\lfloor \frac{s}{10^{2k}} \right\rfloor \bmod 10 = 10-k.$$
Это ровно означает, что цифры в позициях \(10^0,10^2,10^4,\dots,10^{18}\) равны \(0,9,8,\dots,1\). На практике сначала проверяется последняя цифра \(0\), а затем число последовательно делится на \(100\). Каждый такой шаг отбрасывает одну свободную цифру и одну уже проверенную фиксированную цифру, поэтому следующая фиксированная цифра оказывается в разряде единиц.
Если обозначить
$$s_0=s,\qquad s_{r+1}=\left\lfloor \frac{s_r}{100} \right\rfloor,$$
то инвариант можно записать как
$$s_0 \bmod 10 = 0,\qquad s_r \bmod 10 = 10-r \quad (r=1,\dots,9).$$
Это и есть основная идея числового проверяющего шага.
В интервале от \(1010101011\) до \(1389026623\) находится примерно \(3.79\times 10^8\) целых чисел. Однако первое условие позволяет перебирать только кратные \(10\), а второе оставляет из каждой сотни лишь два возможных окончания. В итоге полную проверку проходит лишь около \(7.6\times 10^6\) кандидатов, и для каждого требуется только константное количество операций.
Реализации на C++, Python и Java начинают с вычисления целочисленных границ квадратного корня, следующих из минимального и максимального возможного квадрата. После этого нижняя граница сдвигается к ближайшему кратному \(10\), потому что любое допустимое решение обязано быть таким.
Основной цикл идёт по интервалу с шагом \(10\). Для каждого кандидата сразу проверяются последние две цифры, и любое число, не сравнимое с \(30\) или \(70\) по модулю \(100\), немедленно отбрасывается. Благодаря этому подавляющее большинство вариантов исчезает ещё до проверки маски квадрата.
Для оставшихся кандидатов вычисляется квадрат, после чего запускается арифметическая проверка. Сначала подтверждается последняя цифра \(0\). Затем квадрат многократно делится на \(100\), и каждый раз новая цифра единиц должна быть равна \(9,8,7,\dots,1\). Поскольку требуемый шаблон полностью фиксирован, для этого достаточно короткого цикла и операций над целыми числами.
Поиск завершается сразу после первого полного совпадения. Одна из реализаций дополнительно содержит маленькие контрольные примеры, чтобы убедиться, что проверка шаблона принимает правильный эталон и отвергает близкий неправильный вариант.
Пусть
$$I=\left\lfloor \sqrt{U} \right\rfloor-\left\lceil \sqrt{L} \right\rceil+1.$$
Наивный перебор всех целых чисел из этого диапазона имел бы стоимость \(O(I)\). Здесь асимптотический порядок остаётся линейным по ширине интервала, но константа резко уменьшается: просматриваются только кратные \(10\), а полноценная проверка запускается лишь для чисел, оканчивающихся на \(30\) или \(70\). Поэтому число полных проверок составляет примерно \(I/50\).
Каждая проверка требует вычислить квадрат и выполнить фиксированное число проверок цифр, то есть стоит \(O(1)\). Итак, итоговое время равно \(O(I)\), а память \(O(1)\).
المطلوب هو إيجاد العدد الصحيح الموجب الوحيد \(n\) الذي يكون مربعه على الصورة العشرية 1_2_3_4_5_6_7_8_9_0، بحيث تمثل كل شرطة سفلية رقمًا مجهولًا يمكن أن يكون أي قيمة من \(0\) إلى \(9\). وهذا يعني أن الخانات المثبتة في \(n^2\) هي، من اليمين إلى اليسار، \(0\) ثم \(9\) ثم \(8\) وهكذا حتى \(1\) في الخانة العليا.
الفحص الأعمى لكل الأعداد القريبة ممكن من حيث المبدأ، لكنه يهدر كثيرًا من العمل. لذلك تعتمد الحلول البرمجية على ثلاث أفكار دقيقة: أولًا حصر قيمة الجذر بين حدين شديدي الضيق، ثم استخدام شرط توافقي على آخر رقمين من الجذر، وأخيرًا التحقق من النمط كاملًا بعمليات حسابية صحيحة فقط عبر حذف رقمين في كل خطوة.
القناع العشري نفسه يكشف معظم بنية المسألة. ما إن نعيد صياغته على شكل حدود ومتطابقات توافقية حتى تتحول المهمة من بحث واسع إلى مسح محدود ومصفى بقوة.
إذا جعلنا جميع الخانات المخفية تساوي \(0\)، فإن أصغر مربع ممكن هو
$$L=1020304050607080900.$$
وإذا جعلنا جميعها تساوي \(9\)، فإن أكبر مربع ممكن هو
$$U=1929394959697989990.$$
إذًا لا بد لأي حل صحيح أن يحقق
$$\left\lceil \sqrt{L} \right\rceil \le n \le \left\lfloor \sqrt{U} \right\rfloor,$$
أي عدديًا
$$1010101011 \le n \le 1389026623.$$
وبذلك تنحصر المسألة مباشرة في مجال نهائي ومحدد جدًا.
بما أن المربع المطلوب ينتهي بالرقم \(0\)، فإن \(n^2\) قابل للقسمة على \(10\). والمربع لا ينتهي بـ \(0\) إلا إذا كان الجذر نفسه من مضاعفات \(10\)، لذلك نكتب
$$n=10m.$$
وعندئذٍ يكون
$$m^2=\frac{n^2}{100}$$
منتهيًا بالرقم \(9\)، لأن حذف الصفرين الأخيرين من مربع صالح يكشف الرقم الثابت \(9\). إذن
$$m^2 \equiv 9 \pmod{10}.$$
وبتوافق \(10\)، فإن البواقي الوحيدة التي مربعاتها تساوي \(9\) هي \(3\) و\(7\). لذلك
$$m \equiv 3 \pmod{10} \quad \text{or} \quad m \equiv 7 \pmod{10},$$
ومن ثم بشكل مكافئ
$$n \equiv 30 \pmod{100} \quad \text{or} \quad n \equiv 70 \pmod{100}.$$
هذا هو بالضبط المرشح الذي تستخدمه الشيفرة قبل الانتقال إلى فحص النمط الكامل.
يمكن رؤية هذه الفكرة مباشرة من جدول صغير. إذا انتهى العدد بـ \(10,30,50,70,90\)، فإننا نحصل على
$$10^2 \equiv 100,\quad 30^2 \equiv 900,\quad 50^2 \equiv 500,\quad 70^2 \equiv 900,\quad 90^2 \equiv 100 \pmod{1000}.$$
المربع الصالح يجب أن ينتهي بـ \(900\)، لأن آخر ثلاث خانات فيه على الصورة 9_0. ولذلك لا يبقى إلا العددان المنتهيان بـ \(30\) أو \(70\).
بعد التصفية بالتوافقات، يبقى سؤال واحد: هل يطابق مربع المرشح جميع الخانات المفروضة؟ لا حاجة هنا لتحويل العدد إلى نص. التنفيذ يتحقق من ذلك مباشرة باستعمال القسمة الصحيحة وباقي القسمة.
إذا رمزنا إلى المربع بـ \(s=n^2\)، فإن الصلاحية تكافئ الشرطين
$$s \equiv 0 \pmod{10},$$
ولكل \(k=1,2,\dots,9\)،
$$\left\lfloor \frac{s}{10^{2k}} \right\rfloor \bmod 10 = 10-k.$$
وهذا يعني حرفيًا أن الأرقام في الخانات \(10^0,10^2,10^4,\dots,10^{18}\) يجب أن تكون \(0,9,8,\dots,1\). تنفذ الشيفرة هذا الأمر بطريقة مباشرة: تتحقق أولًا من الصفر الأخير، ثم تقسم المربع على \(100\) مرة بعد مرة. كل قسمة تحذف رقمًا مخفيًا مع رقم ثابت سبق التحقق منه، فينتقل الرقم الثابت التالي إلى خانة الآحاد ويصبح فحصه سهلًا.
إذا عرفنا
$$s_0=s,\qquad s_{r+1}=\left\lfloor \frac{s_r}{100} \right\rfloor,$$
فإن المربع الصالح يجب أن يحقق
$$s_0 \bmod 10 = 0,\qquad s_r \bmod 10 = 10-r \quad (r=1,\dots,9).$$
وهذا هو الثابت الحسابي الأساسي الذي يبني عليه الفاحص العددي.
المجال من \(1010101011\) إلى \(1389026623\) يحتوي تقريبًا على \(3.79\times 10^8\) عددًا صحيحًا. لكن شرط القسمة على \(10\) يسمح بالانتقال بخطوة \(10\)، ثم شرط النهاية \(30\) أو \(70\) بتوافق \(100\) يبقي احتمالين فقط من كل مئة عدد. وهكذا ينخفض عدد المرشحين الذين يحتاجون إلى فحص كامل إلى نحو \(7.6\times 10^6\)، وكل مرشح يتطلب عددًا ثابتًا فقط من العمليات.
تبدأ تطبيقات C++ وPython وJava بحساب حدي الجذر التربيعي الصحيحين الناتجين عن أصغر مربع وأكبر مربع يسمح بهما القناع. ثم يُرفع الحد الأدنى إلى أول مضاعف لـ \(10\)، لأن أي حل صحيح يجب أن يكون كذلك.
تسير الحلقة الرئيسية داخل المجال بخطوة \(10\). ولكل جذر مرشح، تُفحص آخر خانتين فورًا، ويُستبعد كل عدد لا يطابق \(30\) أو \(70\) بتوافق \(100\). بهذه الطريقة تُستبعد الغالبية العظمى من المرشحين قبل حتى حساب المربع بتفصيله الكامل.
إذا نجا المرشح من مرشح النهايات، يُحسب مربعه ثم يبدأ التحقق الحسابي. أولًا تُفحص الخانة الأخيرة \(0\)، ثم يُقسم العدد على \(100\) تكراريًا، ويجب أن تكون خانة الآحاد المكشوفة حديثًا مساوية بالتتابع لـ \(9,8,7,\dots,1\). وبما أن النمط ثابت تمامًا، فإن هذه المرحلة تحتاج فقط إلى حسابات صحيحة وحلقة قصيرة جدًا.
يتوقف البحث فور العثور على أول مرشح ينجح في جميع الاختبارات. كما تتضمن إحدى التنفيذات حالات فحص صغيرة للتأكد من أن آلية التحقق تقبل المثال الصحيح وترفض قيمة قريبة لكنها خاطئة.
لنعرّف
$$I=\left\lfloor \sqrt{U} \right\rfloor-\left\lceil \sqrt{L} \right\rceil+1.$$
الفحص الساذج لكل الأعداد في هذا المجال يكلف \(O(I)\). التنفيذات هنا تبقى خطية من حيث عرض المجال، لكنها تقلص العامل الثابت كثيرًا: فهي تمر فقط على مضاعفات \(10\)، ثم لا تنفذ فحص النمط الكامل إلا على الأعداد التي تنتهي بـ \(30\) أو \(70\). لذلك يكون عدد الفحوص الكاملة تقريبًا \(I/50\).
كل فحص كامل يحتاج إلى تربيع واحد وعدد ثابت من مقارنات الخانات، أي إن كلفته \(O(1)\). ومن ثم فالزمن الكلي \(O(I)\) والذاكرة \(O(1)\).