Among the integers \(1,2,\dots,100\), only the non-squares matter, because perfect squares have rational square roots and are excluded by the statement. For each irrational \(\sqrt{n}\), we read the first 100 digits of its decimal expansion, counting the digit before the decimal point, sum those 100 digits, and then add the 90 resulting digit sums.
The challenge is precision rather than size. Ordinary floating-point arithmetic cannot reliably preserve 100 decimal digits, so the problem has to be reformulated in exact integer terms or handled with guarded arbitrary-precision decimal arithmetic.
The key object is the 100-digit prefix of \(\sqrt{n}\) after removing the decimal point. Since every relevant \(n\) satisfies \(1<n<100\), each irrational square root lies between 1 and 10, so the required block is always one integer digit followed by 99 fractional digits.
For a fixed non-square \(n\), define
$$P_k=\left\lfloor 10^{k-1}\sqrt{n}\right\rfloor \qquad (k\ge 1).$$
Then \(P_1\) is the integer part of \(\sqrt{n}\), \(P_2\) is the first two digits with the decimal point removed, and in general \(P_{100}\) is exactly the 100-digit string required by the problem. If \(s(n)\) denotes the digit sum of \(P_{100}\), then the final quantity is
$$\sum_{\substack{1\le n\le 100\\ n\notin\{1,4,9,16,25,36,49,64,81,100\}}} s(n).$$
Set
$$R_k=10^{2k-2}n-P_k^2.$$
Because \(P_k=\lfloor 10^{k-1}\sqrt{n}\rfloor\), we always have
$$P_k^2\le 10^{2k-2}n < (P_k+1)^2,$$
so \(R_k\) is a nonnegative remainder. To append the next decimal digit, write
$$P_{k+1}=10P_k+x,\qquad x\in\{0,1,\dots,9\},$$
and require \(P_{k+1}^2\le 10^{2k}n\). Expanding the square gives
$$100P_k^2+(20P_k+x)x\le 100(P_k^2+R_k),$$
which is equivalent to
$$ (20P_k+x)x\le 100R_k. $$
Therefore the next correct digit is the largest \(x\in\{0,\dots,9\}\) satisfying this inequality.
Once that maximal digit \(x\) is chosen, the state updates to
$$P_{k+1}=10P_k+x,$$
$$R_{k+1}=10^{2k}n-P_{k+1}^2=100R_k-(20P_k+x)x.$$
This is the classical digit-by-digit square-root algorithm. In the usual handwritten interpretation, each step brings down the next pair \(00\), tests the candidate digits from 9 down to 0, subtracts the best probe, and appends the chosen digit to the growing root prefix.
Start with \(n=2\). The first digit is \(1\) because \(1^2\le 2<2^2\). Hence \(P_1=1\) and \(R_1=2-1^2=1\).
For the next digit, choose the largest \(x\) such that
$$ (20\cdot 1+x)x\le 100. $$
Here \(x=4\) works because \(24\cdot 4=96\), while \(x=5\) fails because \(25\cdot 5=125\). So \(P_2=14\) and \(R_2=100\cdot 1-96=4\).
Repeat once more: choose the largest \(x\) with
$$ (20\cdot 14+x)x\le 400. $$
Now \(x=1\) works and \(x=2\) fails, so \(P_3=141\). Therefore the expansion begins \(1.41\dots\), exactly as expected. Continuing this process to 100 digits gives a digit sum of 475 for \(\sqrt{2}\), which is the checkpoint used by the exact implementation.
The Python and Java implementations compute \(\sqrt{n}\) directly with arbitrary-precision decimal arithmetic instead of reproducing the longhand recurrence. They request 110 significant digits, remove the decimal point, and keep the first 100 characters. Those extra guard digits keep the wanted 100-digit prefix away from the rounding boundary, so the extracted block matches the same mathematical object \(P_{100}\).
All three implementations loop over \(n=1,2,\dots,100\), detect perfect squares with an ordinary integer square root, and skip them because the problem only counts irrational roots.
The C++ implementation follows the exact recurrence above. Its state consists of a current prefix \(P\) and a current remainder \(R\). It performs exactly 100 rounds, multiplies the remainder by 100 after the first digit, searches the next digit from 9 downward using the probe \((20P+d)d\), updates the remainder, appends the chosen digit, and finally sums the digits of the resulting 100-digit integer.
The Python and Java implementations instead rely on arbitrary-precision decimal square roots. They set the working precision to 110 digits, compute \(\sqrt{n}\), convert the result to a plain decimal string, delete the decimal point, take the first 100 digits, and add them. The mechanics differ, but the target is identical: the first 100 digits of \(\sqrt{n}\) written without the decimal point.
Let \(D\) be the number of requested digits and \(L\) the upper limit for \(n\). The exact digit-by-digit method performs \(D\) rounds for each irrational \(n\), and each round tests at most 10 candidate digits. Since the intermediate integers have \(O(D)\) decimal digits, a natural bound is \(O(LD^2)\) elementary digit work with \(O(D)\) memory.
For this problem, \(L=100\) and \(D=100\), so the computation is tiny. The decimal-square-root versions delegate the work to optimized arbitrary-precision libraries at roughly 110-digit precision and are also easily fast enough. The important point is that every implementation avoids binary floating-point shortcuts and keeps enough precision to recover the exact 100-digit prefixes.
Unter den Zahlen \(1,2,\dots,100\) tragen nur die Nichtquadrate bei, denn perfekte Quadrate besitzen rationale Quadratwurzeln und werden laut Aufgabenstellung ausgelassen. Für jedes irrationale \(\sqrt{n}\) lesen wir die ersten 100 Ziffern der Dezimalentwicklung ab, wobei die Ziffer vor dem Komma mitgezählt wird, bilden daraus die Ziffernsumme und addieren anschließend die 90 einzelnen Beiträge.
Die Schwierigkeit liegt nicht in der Anzahl der Fälle, sondern in der Genauigkeit. Gewöhnliche Gleitkommazahlen liefern keine verlässlichen 100 Dezimalstellen, also muss das Problem entweder auf exakte Ganzzahlarithmetik oder auf sauber abgesicherte Dezimalarithmetik mit hoher Präzision zurückgeführt werden.
Das zentrale Objekt ist das 100-stellige Präfix von \(\sqrt{n}\), nachdem das Dezimalkomma entfernt wurde. Für alle relevanten Werte gilt \(1<n<100\), also liegt \(\sqrt{n}\) immer zwischen 1 und 10. Gesucht ist daher stets genau eine Ziffer vor dem Komma und 99 Ziffern danach.
Für ein festes Nichtquadrat \(n\) definieren wir
$$P_k=\left\lfloor 10^{k-1}\sqrt{n}\right\rfloor \qquad (k\ge 1).$$
Dann ist \(P_1\) der ganzzahlige Teil von \(\sqrt{n}\), \(P_2\) sind die ersten beiden Ziffern ohne Komma, und allgemein ist \(P_{100}\) genau der 100-stellige Block aus der Aufgabe. Bezeichnet \(s(n)\) die Ziffernsumme von \(P_{100}\), so lautet die gesuchte Gesamtsumme
$$\sum_{\substack{1\le n\le 100\\ n\notin\{1,4,9,16,25,36,49,64,81,100\}}} s(n).$$
Setze
$$R_k=10^{2k-2}n-P_k^2.$$
Aus \(P_k=\lfloor 10^{k-1}\sqrt{n}\rfloor\) folgt immer
$$P_k^2\le 10^{2k-2}n < (P_k+1)^2,$$
also ist \(R_k\) ein nichtnegativer Rest. Für die nächste Dezimalziffer schreiben wir
$$P_{k+1}=10P_k+x,\qquad x\in\{0,1,\dots,9\},$$
und verlangen \(P_{k+1}^2\le 10^{2k}n\). Nach dem Ausmultiplizieren erhält man
$$100P_k^2+(20P_k+x)x\le 100(P_k^2+R_k),$$
also äquivalent
$$ (20P_k+x)x\le 100R_k. $$
Die nächste korrekte Ziffer ist daher genau die größte Ziffer \(x\in\{0,\dots,9\}\), die diese Ungleichung erfüllt.
Ist diese maximale Ziffer \(x\) gefunden, dann wird der Zustand durch
$$P_{k+1}=10P_k+x,$$
$$R_{k+1}=10^{2k}n-P_{k+1}^2=100R_k-(20P_k+x)x$$
fortgeschrieben. Das ist genau der klassische Ziffer-für-Ziffer-Algorithmus für Quadratwurzeln. In der handschriftlichen Sichtweise zieht man in jedem Schritt das nächste Paar \(00\) herunter, testet die Ziffern von 9 bis 0, subtrahiert den besten zulässigen Wert und hängt die gewählte Ziffer an das bereits bekannte Präfix an.
Wir beginnen mit \(n=2\). Die erste Ziffer ist \(1\), denn \(1^2\le 2<2^2\). Also gilt \(P_1=1\) und \(R_1=2-1^2=1\).
Für die nächste Ziffer suchen wir das größte \(x\) mit
$$ (20\cdot 1+x)x\le 100. $$
Hier funktioniert \(x=4\), weil \(24\cdot 4=96\), aber \(x=5\) scheitert, weil \(25\cdot 5=125\). Damit erhält man \(P_2=14\) und \(R_2=100\cdot 1-96=4\).
Noch einmal wiederholt: Gesucht ist das größte \(x\) mit
$$ (20\cdot 14+x)x\le 400. $$
Nun ist \(x=1\) zulässig und \(x=2\) nicht mehr, also \(P_3=141\). Damit beginnt die Entwicklung als \(1.41\dots\). Führt man das Verfahren bis 100 Ziffern fort, ergibt sich für \(\sqrt{2}\) die Ziffernsumme 475; genau diesen Wert verwendet die exakte Implementierung als Kontrolle.
Die Python- und Java-Implementierungen gehen einen anderen Weg und berechnen \(\sqrt{n}\) direkt mit Dezimalarithmetik beliebiger Präzision. Sie fordern 110 signifikante Stellen an, entfernen das Dezimalkomma und behalten die ersten 100 Zeichen. Diese zusätzlichen Schutzstellen halten das benötigte 100-stellige Präfix von der Rundungsgrenze fern, sodass am Ende derselbe mathematische Block \(P_{100}\) gelesen wird.
Alle drei Implementierungen laufen \(n=1,2,\dots,100\) durch, erkennen perfekte Quadrate mit einer gewöhnlichen ganzzahligen Quadratwurzel und überspringen sie, weil nur irrationale Wurzeln gezählt werden.
Die C++-Implementierung setzt die exakte Rekursion von oben direkt um. Ihr Zustand besteht aus einem aktuellen Präfix \(P\) und einem aktuellen Rest \(R\). Sie führt genau 100 Runden aus, multipliziert den Rest nach der ersten Ziffer jeweils mit 100, sucht die nächste Ziffer von 9 abwärts über den Test \((20P+d)d\), aktualisiert den Rest, hängt die gefundene Ziffer an und summiert am Ende die Ziffern der entstandenen 100-stelligen Ganzzahl.
Die Python- und Java-Implementierungen verlassen sich stattdessen auf Quadratwurzeln mit Dezimalarithmetik beliebiger Präzision. Sie setzen die Arbeitspräzision auf 110 Stellen, berechnen \(\sqrt{n}\), wandeln das Ergebnis in eine normale Dezimaldarstellung um, entfernen das Komma, nehmen die ersten 100 Ziffern und addieren diese. Mechanisch ist das anders, mathematisch zielen aber alle drei Versionen auf dasselbe Objekt: die ersten 100 Ziffern von \(\sqrt{n}\) ohne Dezimalkomma.
Seien \(D\) die gewünschte Ziffernzahl und \(L\) die obere Schranke für \(n\). Die exakte Ziffer-für-Ziffer-Methode benötigt für jedes irrationale \(n\) genau \(D\) Runden, und in jeder Runde werden höchstens 10 Kandidaten geprüft. Da die Zwischenwerte \(O(D)\) Dezimalstellen besitzen, ergibt sich als natürliche Schranke \(O(LD^2)\) elementare Ziffernarbeit bei \(O(D)\) Speicher.
Für dieses Problem ist \(L=100\) und \(D=100\), also ist der Aufwand sehr klein. Die Versionen mit Dezimal-Quadratwurzel delegieren die Arbeit an optimierte Bibliotheken mit ungefähr 110 Stellen Präzision und sind in dieser Größenordnung ebenfalls problemlos schnell. Entscheidend ist, dass keine Implementierung auf ungenaue binäre Gleitkommawerte vertraut.
\(1,2,\dots,100\) aralığındaki sayılardan yalnızca tam kare olmayanlar katkı yapar; çünkü tam karelerin karekökleri rasyoneldir ve soru bunları dışarıda bırakır. Her irrasyonel \(\sqrt{n}\) için ondalık açılımın ilk 100 basamağını, virgülden önceki basamağı da sayarak alır, bu 100 basamağın toplamını bulur ve sonra 90 değerin hepsini toplarız.
Zorluk veri boyutunda değil, hassasiyettedir. Sıradan kayan noktalı aritmetik 100 ondalık basamağı güvenilir biçimde koruyamaz; bu yüzden problem ya tam sayı aritmetiğine çevrilmeli ya da koruma basamakları bulunan yüksek hassasiyetli ondalık aritmetik ile çözülmelidir.
Merkezdeki nesne, ondalık ayıracı kaldırılmış hâliyle \(\sqrt{n}\)'in 100 basamaklı ön ekidir. İlgili tüm \(n\) değerleri için \(1<n<100\) olduğundan \(\sqrt{n}\) her zaman 1 ile 10 arasındadır. Dolayısıyla istenen blok, bir tam kısım basamağı ve ardından gelen 99 kesir basamağından oluşur.
Sabit bir tam kare olmayan \(n\) için
$$P_k=\left\lfloor 10^{k-1}\sqrt{n}\right\rfloor \qquad (k\ge 1)$$
tanımını yapalım. Buna göre \(P_1\), \(\sqrt{n}\)'in tam kısmıdır; \(P_2\), ondalık ayracı kaldırılmış ilk iki basamaktır; genel olarak \(P_{100}\) ise soruda istenen tam 100 basamaklı bloktur. \(P_{100}\)'ün rakamları toplamını \(s(n)\) ile gösterirsek toplam hedef
$$\sum_{\substack{1\le n\le 100\\ n\notin\{1,4,9,16,25,36,49,64,81,100\}}} s(n)$$
olur.
Şimdi
$$R_k=10^{2k-2}n-P_k^2$$
olsun. \(P_k=\lfloor 10^{k-1}\sqrt{n}\rfloor\) tanımından dolayı her zaman
$$P_k^2\le 10^{2k-2}n < (P_k+1)^2$$
eşitsizliği vardır; yani \(R_k\) negatif olmayan bir kalandır. Bir sonraki basamağı eklemek için
$$P_{k+1}=10P_k+x,\qquad x\in\{0,1,\dots,9\}$$
yazar ve \(P_{k+1}^2\le 10^{2k}n\) koşulunu isteriz. Kareyi açınca
$$100P_k^2+(20P_k+x)x\le 100(P_k^2+R_k)$$
elde edilir; bu da
$$ (20P_k+x)x\le 100R_k $$
şartına denktir. Demek ki bir sonraki doğru basamak, bu eşitsizliği sağlayan en büyük \(x\) rakamıdır.
Bu en büyük \(x\) seçildikten sonra durum
$$P_{k+1}=10P_k+x,$$
$$R_{k+1}=10^{2k}n-P_{k+1}^2=100R_k-(20P_k+x)x$$
şeklinde güncellenir. Bu, klasik basamak basamak karekök çıkarma yöntemidir. El hesabı yorumunda her adımda sıradaki \(00\) çifti aşağı indirilir, 9'dan 0'a kadar olası rakamlar denenir, en büyük uygun deneme çıkarılır ve seçilen rakam kökün ön ekine eklenir.
\(n=2\) ile başlayalım. İlk basamak \(1\)'dir, çünkü \(1^2\le 2<2^2\). O hâlde \(P_1=1\) ve \(R_1=2-1^2=1\).
İkinci basamak için en büyük
$$ (20\cdot 1+x)x\le 100 $$
koşulunu sağlayan \(x\) aranır. \(x=4\) uygundur, çünkü \(24\cdot 4=96\); ama \(x=5\) uygun değildir, çünkü \(25\cdot 5=125\). Böylece \(P_2=14\) ve \(R_2=100\cdot 1-96=4\).
Bir kez daha tekrar edelim:
$$ (20\cdot 14+x)x\le 400. $$
Burada \(x=1\) olur, \(x=2\) ise fazla büyüktür. Dolayısıyla \(P_3=141\) ve açılım \(1.41\dots\) diye başlar. Süreç 100 basamağa kadar sürdürüldüğünde \(\sqrt{2}\) için rakamlar toplamı 475 çıkar; tam yöntem bunu kontrol noktası olarak kullanır.
Python ve Java uygulamaları uzun işlem yinelemesini doğrudan kurmak yerine \(\sqrt{n}\)'i keyfi hassasiyetli ondalık aritmetik ile hesaplar. 110 anlamlı basamak ister, ondalık ayıracı kaldırır ve ilk 100 karakteri alırlar. Bu ek koruma basamakları, istenen 100 basamaklı ön eki yuvarlama sınırından uzak tuttuğu için elde edilen blok yine aynı matematiksel nesne olan \(P_{100}\) olur.
Üç uygulama da \(n=1,2,\dots,100\) üzerinde döner, sıradan bir tam sayı karekök testiyle tam kareleri saptar ve soru yalnızca irrasyonel kökleri istediği için bunları atlar.
C++ uygulaması yukarıdaki tam yinelemeyi izler. Durumu bir kök ön eki \(P\) ile bir kalan \(R\) belirler. Tam olarak 100 tur çalışır; ilk basamaktan sonra kalanı her adımda 100 ile çarpar, \((20P+d)d\) denemesiyle bir sonraki rakamı 9'dan aşağı doğru arar, kalanı günceller, rakamı eke yazar ve sonunda oluşan 100 basamaklı tam sayının rakamlarını toplar.
Python ve Java uygulamaları ise keyfi hassasiyetli ondalık karekök rutinlerine dayanır. Çalışma hassasiyetini 110 basamak yapar, \(\sqrt{n}\)'i hesaplar, sonucu düz bir ondalık yazıya çevirir, noktayı siler, ilk 100 basamağı alır ve toplar. Mekanik ayrıntılar farklı olsa da hedef aynıdır: \(\sqrt{n}\)'in ondalık ayıracı kaldırılmış ilk 100 basamağı.
\(D\) istenen basamak sayısı, \(L\) ise \(n\) için üst sınır olsun. Tam basamak çıkarma yöntemi her irrasyonel \(n\) için \(D\) tur yapar ve her turda en fazla 10 aday rakam dener. Ara değerler \(O(D)\) ondalık basamak taşıdığı için doğal karmaşıklık sınırı \(O(LD^2)\) temel basamak işlemi ve \(O(D)\) bellektir.
Bu problemde \(L=100\) ve \(D=100\) olduğundan maliyet çok küçüktür. Ondalık karekök kullanan sürümler de yaklaşık 110 basamaklık optimize kütüphanelere işi bıraktıkları için fazlasıyla hızlıdır. Asıl önemli nokta, hiçbir sürümün yetersiz ikili kayan nokta yaklaşımına güvenmemesidir.
Entre los enteros \(1,2,\dots,100\), solo contribuyen los no cuadrados, porque los cuadrados perfectos tienen raíces cuadradas racionales y el enunciado los excluye. Para cada \(\sqrt{n}\) irracional, tomamos los primeros 100 dígitos de su expansión decimal, contando también el dígito anterior al punto decimal, calculamos la suma de esos 100 dígitos y luego sumamos las 90 contribuciones obtenidas.
La dificultad no está en el tamaño de la entrada, sino en la precisión. La aritmética de punto flotante ordinaria no conserva de forma fiable 100 cifras decimales, así que el problema debe reformularse en términos enteros exactos o resolverse con aritmética decimal de alta precisión protegida con dígitos extra.
El objeto central es el prefijo de 100 dígitos de \(\sqrt{n}\) después de eliminar el punto decimal. Para todos los valores relevantes se cumple \(1<n<100\), de modo que \(\sqrt{n}\) siempre está entre 1 y 10. Por eso el bloque pedido contiene exactamente un dígito entero y 99 dígitos fraccionarios.
Para un no cuadrado fijo \(n\), definimos
$$P_k=\left\lfloor 10^{k-1}\sqrt{n}\right\rfloor \qquad (k\ge 1).$$
Entonces \(P_1\) es la parte entera de \(\sqrt{n}\), \(P_2\) son los dos primeros dígitos sin el punto decimal y, en general, \(P_{100}\) es exactamente el bloque de 100 dígitos pedido por el problema. Si \(s(n)\) es la suma de dígitos de \(P_{100}\), el total buscado es
$$\sum_{\substack{1\le n\le 100\\ n\notin\{1,4,9,16,25,36,49,64,81,100\}}} s(n).$$
Definimos
$$R_k=10^{2k-2}n-P_k^2.$$
Como \(P_k=\lfloor 10^{k-1}\sqrt{n}\rfloor\), siempre se cumple
$$P_k^2\le 10^{2k-2}n < (P_k+1)^2,$$
así que \(R_k\) es un resto no negativo. Para añadir el siguiente dígito decimal escribimos
$$P_{k+1}=10P_k+x,\qquad x\in\{0,1,\dots,9\},$$
y exigimos \(P_{k+1}^2\le 10^{2k}n\). Al expandir el cuadrado obtenemos
$$100P_k^2+(20P_k+x)x\le 100(P_k^2+R_k),$$
equivalente a
$$ (20P_k+x)x\le 100R_k. $$
Por tanto, el siguiente dígito correcto es el mayor \(x\in\{0,\dots,9\}\) que satisface esa desigualdad.
Una vez elegido ese dígito máximo \(x\), el estado se actualiza como
$$P_{k+1}=10P_k+x,$$
$$R_{k+1}=10^{2k}n-P_{k+1}^2=100R_k-(20P_k+x)x.$$
Este es el algoritmo clásico de raíz cuadrada dígito a dígito. En la interpretación manual, cada paso baja el siguiente par \(00\), prueba los dígitos de 9 a 0, resta la mejor prueba válida y añade el dígito elegido al prefijo de la raíz.
Tomemos \(n=2\). El primer dígito es \(1\), porque \(1^2\le 2<2^2\). Así, \(P_1=1\) y \(R_1=2-1^2=1\).
Para el siguiente dígito buscamos el mayor \(x\) tal que
$$ (20\cdot 1+x)x\le 100. $$
Aquí \(x=4\) sirve, pues \(24\cdot 4=96\), mientras que \(x=5\) falla porque \(25\cdot 5=125\). Por tanto, \(P_2=14\) y \(R_2=100\cdot 1-96=4\).
Repetimos una vez más:
$$ (20\cdot 14+x)x\le 400. $$
Ahora \(x=1\) funciona y \(x=2\) ya no, de modo que \(P_3=141\). La expansión comienza entonces como \(1.41\dots\), tal como debe ser. Si seguimos hasta 100 dígitos, la suma de dígitos para \(\sqrt{2}\) es 475, que aparece como comprobación en la implementación exacta.
Las implementaciones en Python y Java no reproducen explícitamente la recurrencia anterior; calculan \(\sqrt{n}\) directamente con aritmética decimal de precisión arbitraria. Piden 110 cifras significativas, eliminan el punto decimal y conservan los primeros 100 caracteres. Esos dígitos de guarda mantienen el prefijo buscado lejos del borde de redondeo, así que el bloque extraído coincide con el mismo objeto matemático \(P_{100}\).
Las tres implementaciones recorren \(n=1,2,\dots,100\), detectan cuadrados perfectos con una raíz cuadrada entera ordinaria y los omiten porque el problema solo cuenta raíces irracionales.
La implementación en C++ sigue exactamente la recurrencia anterior. Su estado es un prefijo actual \(P\) y un resto actual \(R\). Ejecuta 100 rondas, multiplica el resto por 100 después del primer dígito, busca el siguiente dígito desde 9 hacia abajo usando la prueba \((20P+d)d\), actualiza el resto, añade el dígito elegido y finalmente suma las cifras del entero de 100 dígitos obtenido.
Las implementaciones en Python y Java se apoyan en raíces cuadradas decimales de precisión arbitraria. Fijan la precisión de trabajo en 110 dígitos, calculan \(\sqrt{n}\), convierten el resultado en una cadena decimal normal, eliminan el punto, toman los primeros 100 dígitos y los suman. La mecánica cambia, pero el objetivo es el mismo: los primeros 100 dígitos de \(\sqrt{n}\) escritos sin punto decimal.
Sea \(D\) el número de dígitos pedidos y \(L\) el límite superior para \(n\). El método exacto dígito a dígito realiza \(D\) rondas por cada \(n\) irracional, y en cada ronda prueba como máximo 10 candidatos. Como los enteros intermedios tienen \(O(D)\) dígitos decimales, una cota natural es \(O(LD^2)\) trabajo elemental sobre dígitos con \(O(D)\) memoria.
En este problema, \(L=100\) y \(D=100\), así que el coste es minúsculo. Las versiones basadas en raíces cuadradas decimales delegan el trabajo en bibliotecas optimizadas a unas 110 cifras de precisión y también son más que suficientes. Lo importante es que ninguna implementación depende de aproximaciones binarias de baja precisión.
在整数 \(1,2,\dots,100\) 中，只有非完全平方数需要计入，因为完全平方数的平方根是有理数，而题目明确把它们排除。对每个无理数平方根 \(\sqrt{n}\)，我们取它十进制展开的前 100 个数字，连同小数点前的那一位一起计算，求出这 100 个数字的数位和，再把 90 个这样的结果全部加起来。
这道题的难点不在规模，而在精度。普通浮点数无法可靠地保留 100 位十进制数字，因此必须把问题改写成精确的整数计算，或者使用带有保护位的高精度十进制运算。
核心对象是去掉小数点之后 \(\sqrt{n}\) 的前 100 位数字。对所有相关的 \(n\) 都有 \(1<n<100\)，所以 \(\sqrt{n}\) 一定落在 1 和 10 之间。于是题目要求的块总是“1 位整数部分 + 99 位小数部分”。
对固定的非完全平方数 \(n\)，定义
$$P_k=\left\lfloor 10^{k-1}\sqrt{n}\right\rfloor \qquad (k\ge 1).$$
那么 \(P_1\) 是 \(\sqrt{n}\) 的整数部分，\(P_2\) 是去掉小数点后的前两位，而一般地，\(P_{100}\) 就是题目要求的整整 100 位数字。若用 \(s(n)\) 表示 \(P_{100}\) 的数位和，那么最终答案就是
$$\sum_{\substack{1\le n\le 100\\ n\notin\{1,4,9,16,25,36,49,64,81,100\}}} s(n).$$
再定义
$$R_k=10^{2k-2}n-P_k^2.$$
由于 \(P_k=\lfloor 10^{k-1}\sqrt{n}\rfloor\)，始终有
$$P_k^2\le 10^{2k-2}n < (P_k+1)^2,$$
因此 \(R_k\) 总是一个非负余量。要追加下一位数字，写成
$$P_{k+1}=10P_k+x,\qquad x\in\{0,1,\dots,9\},$$
并要求 \(P_{k+1}^2\le 10^{2k}n\)。把平方展开得到
$$100P_k^2+(20P_k+x)x\le 100(P_k^2+R_k),$$
也就是
$$ (20P_k+x)x\le 100R_k. $$
所以，下一位正确数字就是满足这个不等式的最大十进制数字 \(x\)。
选出这个最大数字 \(x\) 之后，状态更新为
$$P_{k+1}=10P_k+x,$$
$$R_{k+1}=10^{2k}n-P_{k+1}^2=100R_k-(20P_k+x)x.$$
这正是经典的逐位开平方算法。从手算的角度看，每一步都把下一对 \(00\)“落下来”，从 9 到 0 测试候选数字，减去最大的可行试探值，然后把该数字接到当前根前缀的末尾。
先看 \(n=2\)。第一位数字是 \(1\)，因为 \(1^2\le 2<2^2\)。于是 \(P_1=1\)，\(R_1=2-1^2=1\)。
第二位数字需要满足
$$ (20\cdot 1+x)x\le 100. $$
其中 \(x=4\) 可行，因为 \(24\cdot 4=96\)；但 \(x=5\) 不行，因为 \(25\cdot 5=125\)。因此 \(P_2=14\)，\(R_2=100\cdot 1-96=4\)。
再做一步，需要最大的 \(x\) 满足
$$ (20\cdot 14+x)x\le 400. $$
这时 \(x=1\) 可行而 \(x=2\) 不可行，所以 \(P_3=141\)。于是展开一开始就是 \(1.41\dots\)。如果把这个过程继续到 100 位，\(\sqrt{2}\) 的前 100 位数字和是 475，这也是精确实现里使用的校验点。
Python 和 Java 的实现没有显式重现上面的逐位递推，而是直接用任意精度十进制运算计算 \(\sqrt{n}\)。它们请求 110 位有效数字，删除小数点，再保留前 100 个字符。额外的保护位把所需的 100 位前缀与舍入边界隔开，因此提取出来的块仍然对应同一个数学对象 \(P_{100}\)。
三个实现都会遍历 \(n=1,2,\dots,100\)，先用普通整数平方根判断是否为完全平方数，如果是就跳过，因为题目只统计无理平方根。
C++ 实现直接执行上面的精确递推。它维护当前前缀 \(P\) 和当前余量 \(R\)，总共做 100 轮；在第一位之后，每轮都先把余量乘以 100，再用 \((20P+d)d\) 这个试探式从 9 往下寻找下一位，更新余量，追加该位数字，最后对得到的 100 位整数做数位求和。
Python 和 Java 实现则依赖任意精度十进制平方根。它们把工作精度设为 110 位，计算 \(\sqrt{n}\)，转成普通十进制字符串，删掉小数点，取前 100 位并求和。实现机制不同，但目标完全一致：得到去掉小数点之后 \(\sqrt{n}\) 的前 100 位数字。
设所需数字位数为 \(D\)，\(n\) 的上界为 \(L\)。精确的逐位算法对每个无理数 \(n\) 执行 \(D\) 轮，而每轮最多只测试 10 个候选数字。由于中间整数具有 \(O(D)\) 位十进制数字，一个自然的上界是 \(O(LD^2)\) 的基础数位操作量，空间复杂度为 \(O(D)\)。
在本题中，\(L=100\)，\(D=100\)，因此计算量极小。使用十进制高精度平方根的版本把主要工作交给大约 110 位精度的优化库，在这个规模下同样非常轻松。真正关键的是：所有实现都避开了不可靠的二进制浮点近似。
Среди чисел \(1,2,\dots,100\) вклад дают только неполные квадраты, потому что квадратные корни из совершенных квадратов рациональны и по условию исключаются. Для каждого иррационального \(\sqrt{n}\) нужно взять первые 100 цифр десятичной записи, считая и цифру перед десятичной точкой, найти сумму этих 100 цифр, а затем сложить все 90 полученных значений.
Трудность здесь не в размере входа, а в точности. Обычная арифметика с плавающей запятой не сохраняет надежно 100 десятичных цифр, поэтому задачу нужно переводить либо в точные целочисленные вычисления, либо в десятичную арифметику произвольной точности с запасом по разрядам.
Главный объект — это первые 100 цифр \(\sqrt{n}\) после удаления десятичной точки. Для всех нужных значений выполняется \(1<n<100\), значит \(\sqrt{n}\) всегда лежит между 1 и 10. Следовательно, искомый блок состоит из одной цифры целой части и 99 цифр дробной части.
Для фиксированного неполного квадрата \(n\) введем
$$P_k=\left\lfloor 10^{k-1}\sqrt{n}\right\rfloor \qquad (k\ge 1).$$
Тогда \(P_1\) — это целая часть \(\sqrt{n}\), \(P_2\) — первые две цифры без десятичной точки, а вообще \(P_{100}\) есть ровно тот 100-значный блок, который требуется в задаче. Если \(s(n)\) обозначает сумму цифр числа \(P_{100}\), то итоговая величина равна
$$\sum_{\substack{1\le n\le 100\\ n\notin\{1,4,9,16,25,36,49,64,81,100\}}} s(n).$$
Положим
$$R_k=10^{2k-2}n-P_k^2.$$
Так как \(P_k=\lfloor 10^{k-1}\sqrt{n}\rfloor\), всегда верно
$$P_k^2\le 10^{2k-2}n < (P_k+1)^2,$$
поэтому \(R_k\) — неотрицательный остаток. Чтобы добавить следующую цифру, пишем
$$P_{k+1}=10P_k+x,\qquad x\in\{0,1,\dots,9\},$$
и требуем \(P_{k+1}^2\le 10^{2k}n\). После раскрытия квадрата получаем
$$100P_k^2+(20P_k+x)x\le 100(P_k^2+R_k),$$
то есть эквивалентно
$$ (20P_k+x)x\le 100R_k. $$
Следующая правильная цифра — это наибольшая цифра \(x\in\{0,\dots,9\}\), удовлетворяющая этому неравенству.
После выбора максимальной цифры \(x\) состояние обновляется так:
$$P_{k+1}=10P_k+x,$$
$$R_{k+1}=10^{2k}n-P_{k+1}^2=100R_k-(20P_k+x)x.$$
Это и есть классический алгоритм извлечения квадратного корня по цифрам. В рукописной интерпретации на каждом шаге вниз сносится следующая пара \(00\), цифры от 9 до 0 проверяются как кандидаты, лучший допустимый пробный член вычитается, а выбранная цифра приписывается к уже найденному префиксу корня.
Начнем с \(n=2\). Первая цифра равна \(1\), потому что \(1^2\le 2<2^2\). Следовательно, \(P_1=1\) и \(R_1=2-1^2=1\).
Для следующей цифры ищем наибольшее \(x\), для которого
$$ (20\cdot 1+x)x\le 100. $$
Здесь подходит \(x=4\), так как \(24\cdot 4=96\), а \(x=5\) уже не подходит, потому что \(25\cdot 5=125\). Значит, \(P_2=14\) и \(R_2=100\cdot 1-96=4\).
Повторяем еще раз:
$$ (20\cdot 14+x)x\le 400. $$
Теперь подходит \(x=1\), а \(x=2\) уже слишком велик, поэтому \(P_3=141\). Значит, разложение начинается как \(1.41\dots\). Если продолжить процесс до 100 цифр, сумма цифр для \(\sqrt{2}\) равна 475; именно это значение используется как контрольная точка в точной реализации.
Реализации на Python и Java не воспроизводят описанную рекурсию явно, а вычисляют \(\sqrt{n}\) напрямую с помощью десятичной арифметики произвольной точности. Они запрашивают 110 значащих цифр, удаляют десятичную точку и оставляют первые 100 символов. Эти дополнительные защитные цифры отодвигают нужный префикс от границы округления, так что извлеченный блок совпадает с тем же математическим объектом \(P_{100}\).
Все три реализации перебирают \(n=1,2,\dots,100\), находят совершенные квадраты с помощью обычного целочисленного квадратного корня и пропускают их, потому что задача учитывает только иррациональные корни.
Реализация на C++ буквально следует точной рекурсии выше. Ее состояние — текущий префикс \(P\) и текущий остаток \(R\). Она выполняет ровно 100 шагов, после первой цифры умножает остаток на 100, ищет следующую цифру сверху вниз с помощью проверки \((20P+d)d\), обновляет остаток, дописывает найденную цифру и в конце суммирует цифры полученного 100-значного целого числа.
Реализации на Python и Java опираются на десятичные квадратные корни произвольной точности. Они выставляют рабочую точность 110 цифр, вычисляют \(\sqrt{n}\), переводят результат в обычную десятичную строку, удаляют точку, берут первые 100 цифр и суммируют их. Механика различается, но математическая цель одна и та же: первые 100 цифр числа \(\sqrt{n}\) без десятичной точки.
Пусть \(D\) — число требуемых цифр, а \(L\) — верхняя граница для \(n\). Точный поразрядный метод делает \(D\) шагов для каждого иррационального \(n\), и на каждом шаге проверяет не более 10 кандидатов. Поскольку промежуточные целые числа имеют \(O(D)\) десятичных цифр, естественная оценка равна \(O(LD^2)\) элементарных операций над цифрами при \(O(D)\) памяти.
В этой задаче \(L=100\) и \(D=100\), так что вычисление очень маленькое. Версии с десятичным квадратным корнем передают основную работу оптимизированным библиотекам примерно на 110 цифрах точности и тоже работают мгновенно. Главное — ни одна реализация не полагается на грубые двоичные приближения с плавающей запятой.
من بين الأعداد \(1,2,\dots,100\)، لا تسهم إلا الأعداد غير المربعة، لأن الجذور التربيعية للمربعات الكاملة نسبية، والمسألة تستبعدها صراحة. لكل \(\sqrt{n}\) غير نسبي، نأخذ أول 100 رقم من توسعه العشري مع احتساب الرقم الواقع قبل الفاصلة العشرية، ثم نحسب مجموع هذه الأرقام المئة، وبعد ذلك نجمع القيم الناتجة لجميع الحالات التسعين.
الصعوبة هنا ليست في حجم المعطيات بل في الدقة. الحساب العشري العائم العادي لا يحافظ بشكل موثوق على 100 منزلة عشرية، لذلك يجب إعادة صياغة المسألة إما على صورة حسابات صحيحة تامة، أو باستخدام حساب عشري عالي الدقة مع منازل احتياطية إضافية.
الشيء الرياضي المركزي هو أول 100 رقم من \(\sqrt{n}\) بعد حذف الفاصلة العشرية. ولكل قيمة مهمة من \(n\) لدينا \(1<n<100\)، ولذلك يكون \(\sqrt{n}\) دائمًا بين 1 و10. هذا يعني أن الكتلة المطلوبة تتكون دائمًا من رقم واحد في الجزء الصحيح و99 رقمًا بعد الفاصلة.
لعدد غير مربع ثابت \(n\)، نعرّف
$$P_k=\left\lfloor 10^{k-1}\sqrt{n}\right\rfloor \qquad (k\ge 1).$$
عندئذ يكون \(P_1\) هو الجزء الصحيح من \(\sqrt{n}\)، ويكون \(P_2\) هو أول رقمين بعد حذف الفاصلة، وبصورة عامة فإن \(P_{100}\) هو بالضبط المقطع المكوّن من 100 رقم الذي تطلبه المسألة. وإذا رمزنا إلى مجموع أرقام \(P_{100}\) بالرمز \(s(n)\)، فإن المقدار النهائي هو
$$\sum_{\substack{1\le n\le 100\\ n\notin\{1,4,9,16,25,36,49,64,81,100\}}} s(n).$$
لنضع
$$R_k=10^{2k-2}n-P_k^2.$$
وبما أن \(P_k=\lfloor 10^{k-1}\sqrt{n}\rfloor\)، فنحن نملك دائمًا
$$P_k^2\le 10^{2k-2}n < (P_k+1)^2,$$
ومن ثم فإن \(R_k\) باقٍ غير سالب. ولإضافة الرقم العشري التالي نكتب
$$P_{k+1}=10P_k+x,\qquad x\in\{0,1,\dots,9\},$$
ونفرض الشرط \(P_{k+1}^2\le 10^{2k}n\). وبعد توسيع المربع نحصل على
$$100P_k^2+(20P_k+x)x\le 100(P_k^2+R_k),$$
أي بصورة مكافئة
$$ (20P_k+x)x\le 100R_k. $$
إذن الرقم الصحيح التالي هو أكبر رقم عشري \(x\) يحقق هذه المتباينة.
بعد اختيار أكبر رقم ممكن \(x\)، تتحدث الحالة وفق
$$P_{k+1}=10P_k+x,$$
$$R_{k+1}=10^{2k}n-P_{k+1}^2=100R_k-(20P_k+x)x.$$
وهذه هي خوارزمية استخراج الجذر التربيعي التقليدية رقمًا رقمًا. وفي التفسير اليدوي المعتاد، تنزل في كل خطوة الزوج التالي \(00\)، وتُجرَّب الأرقام من 9 حتى 0، ثم يُطرح أفضل اختبار صالح، ويُلحق الرقم المختار بالمقدمة الحالية للجذر.
نبدأ بـ \(n=2\). الرقم الأول هو \(1\)، لأن \(1^2\le 2<2^2\). لذلك \(P_1=1\) و\(R_1=2-1^2=1\).
ولإيجاد الرقم التالي نبحث عن أكبر \(x\) يحقق
$$ (20\cdot 1+x)x\le 100. $$
نجد أن \(x=4\) صالح لأن \(24\cdot 4=96\)، بينما \(x=5\) غير صالح لأن \(25\cdot 5=125\). إذن \(P_2=14\) و\(R_2=100\cdot 1-96=4\).
نكرر العملية مرة أخرى ونطلب أكبر \(x\) بحيث
$$ (20\cdot 14+x)x\le 400. $$
الآن ينجح \(x=1\) ويفشل \(x=2\)، ومن ثم \(P_3=141\). وبذلك تبدأ الكتابة العشرية على صورة \(1.41\dots\) كما ينبغي. وإذا واصلنا حتى 100 رقم، يكون مجموع أرقام \(\sqrt{2}\) مساويًا لـ 475، وهو فحص تستخدمه الطريقة الدقيقة.
تنفذ تطبيقا Python وJava الحساب بطريقة مختلفة؛ إذ يحسبان \(\sqrt{n}\) مباشرة باستعمال حساب عشري ذي دقة اعتباطية بدل بناء العلاقة التكرارية يدويًا. يطلبان 110 أرقام معنوية، ثم يحذفان الفاصلة العشرية ويحتفظان بأول 100 محرف. هذه الأرقام الاحتياطية الإضافية تُبعد المقدمة المطلوبة عن حد التقريب، ولذلك يطابق المقطع المستخرج الكائن الرياضي نفسه \(P_{100}\).
تجتاز التطبيقات الثلاثة القيم \(n=1,2,\dots,100\)، وتتعرف على المربعات الكاملة بواسطة جذر تربيعي صحيح عادي، ثم تتجاوزها لأن المسألة لا تعد إلا الجذور غير النسبية.
يتبع تطبيق C++ العلاقة الدقيقة السابقة حرفيًا. حالته تتكون من مقدمة حالية \(P\) وباقٍ حالي \(R\). ينفذ 100 دورة بالضبط، ويضرب الباقي في 100 بعد الرقم الأول، ثم يبحث عن الرقم التالي من 9 نزولًا باستخدام الاختبار \((20P+d)d\)، ويحدث الباقي، ويلحق الرقم المختار، ثم يجمع في النهاية أرقام العدد الصحيح ذي المئة رقم الناتج.
أما تطبيقا Python وJava فيعتمدان على جذور تربيعية عشرية عالية الدقة. يضبطان دقة العمل على 110 أرقام، ويحسبان \(\sqrt{n}\)، ويحولان النتيجة إلى سلسلة عشرية عادية، ويحذفان الفاصلة، ثم يأخذان أول 100 رقم ويجمعانها. تختلف الآلية التنفيذية، لكن الهدف الرياضي واحد: أول 100 رقم من \(\sqrt{n}\) بعد حذف الفاصلة العشرية.
إذا كان \(D\) هو عدد الأرقام المطلوبة و\(L\) هو الحد الأعلى لـ \(n\)، فإن الطريقة الدقيقة رقمًا رقمًا تنفذ \(D\) خطوة لكل \(n\) غير مربع، وفي كل خطوة تختبر على الأكثر 10 أرقام مرشحة. ولأن القيم الوسيطة تحتوي على \(O(D)\) أرقام عشرية، فإن حدًا طبيعيًا للتعقيد هو \(O(LD^2)\) من العمليات الأولية على الأرقام مع ذاكرة مقدارها \(O(D)\).
في هذه المسألة لدينا \(L=100\) و\(D=100\)، لذلك يكون الحساب صغيرًا جدًا. أما النسخ التي تستخدم الجذر التربيعي العشري فتفوض العمل إلى مكتبات محسنة عند دقة تقارب 110 أرقام، وهي أيضًا سريعة جدًا على هذا المقياس. المهم أن جميع الحلول تتجنب الاعتماد على تقريب ثنائي منخفض الدقة.