Fix the prime base
$$p=10^9+7.$$
For each \(d\in\{1,2,\dots,100000\}\), the implementation studies the digit
$$a=p-d,$$
so it is really searching among the \(100000\) largest nonzero base-\(p\) digits. Define
$$M_p(a)=\min\{m\ge 1:\text{the base-}p\text{ expansion of }m^2\text{ contains the digit }a\}.$$
The computed quantity is therefore
$$\sum_{d=1}^{100000} M_p(p-d).$$
A direct search is hopeless because the first valid square can be on the scale of \(p\), so the solution turns the digit condition into modular and interval conditions.
The key observation is that a fixed digit in a fixed base corresponds to a family of arithmetic intervals, and for the specific digits \(a=p-d\) those intervals collapse to only two relevant cases.
A digit \(a\) appears in the base-\(p\) expansion of an integer \(N\) at position \(k\ge 0\) exactly when there exists an integer \(t\ge 0\) such that
$$a\,p^k+t\,p^{k+1}\le N\le a\,p^k+t\,p^{k+1}+p^k-1.$$
Applying this to \(N=m^2\), every possible occurrence of \(a\) inside a square is equivalent to asking whether some interval of that form contains a perfect square.
For fixed \(k\) and \(t\), the smallest candidate square root is always
$$m=\left\lceil\sqrt{a\,p^k+t\,p^{k+1}}\right\rceil.$$
So the whole problem is reduced to finding the first interval whose lower endpoint rounds up to a square still inside the same interval.
Here the target digit is \(a=p-d\) with \(1\le d\le 100000\), so \(a\) is very close to \(p\) and in particular
$$a>\frac{p}{2}.$$
If \(a\) appears in the unit position (\(k=0\)), then we only need a congruence modulo \(p\).
If instead \(a\) appears at any higher position (\(k\ge 1\)), then
$$m^2\ge a\,p>\frac{p^2}{2},$$
hence
$$m>\frac{p}{\sqrt{2}}>\frac{p}{2}.$$
This matters because any square root found modulo \(p\) can be represented by a positive integer at most \(p/2\). Therefore:
If the unit-digit case is possible, it automatically gives the global minimum.
If the unit-digit case is impossible, then the smallest remaining possibility is the \(p\)-digit (\(k=1\)); positions \(k\ge 2\) are much larger still.
To place the digit \(a\) in the unit position, we need
$$m^2\equiv a \pmod p.$$
Euler's criterion decides whether this congruence has a solution:
$$a^{(p-1)/2}\equiv 1 \pmod p \iff a\text{ is a quadratic residue mod }p.$$
Because
$$p\equiv 3\pmod 4,$$
a square root is given directly by
$$r\equiv a^{(p+1)/4}\pmod p.$$
The two residue-class solutions are \(r\) and \(p-r\), so the smallest positive integer producing the digit \(a\) in the final base-\(p\) digit is
$$M_p(a)=\min(r,p-r).$$
No larger-position occurrence can beat this, because every larger-position occurrence already needs \(m>p/\sqrt2\).
If \(a\) is not a quadratic residue modulo \(p\), then the unit-digit case is impossible. The first possible place is therefore the coefficient of \(p\), so we look for squares in intervals
$$I_t=[a\,p+t\,p^2,\ a\,p+t\,p^2+p-1]\qquad (t\ge 0).$$
Since \(a=p-d\), the lower endpoint becomes
$$L_t=a\,p+t\,p^2=p^2-dp+t\,p^2.$$
For a fixed \(t\), the smallest square that could possibly land in the interval is
$$m_t=\left\lceil\sqrt{L_t}\right\rceil.$$
The interval contains a square exactly when
$$m_t^2\le L_t+p-1.$$
The first \(t\) satisfying this condition yields the global minimum, because the intervals are strictly increasing with \(t\).
A small residue example is base \(11\) with target digit \(9\). Since
$$9\equiv 3^2\pmod{11},$$
the smallest positive representative is \(3\), and indeed
$$3^2=9,$$
so \(M_{11}(9)=3\).
A small non-residue example is base \(11\) with target digit \(10\). Here \(10\) is not a square modulo \(11\), so the unit-digit case is impossible. We must search the \(11\)-digit intervals:
$$[110,120],\qquad [231,241],\qquad [352,362],\dots$$
The corresponding ceiling square roots are
$$11,\qquad 16,\qquad 19.$$
The first two squares miss their intervals, because
$$11^2=121>120,\qquad 16^2=256>241.$$
The third one works:
$$19^2=361\in[352,362].$$
In base \(11\), this is
$$361=2\cdot 11^2+10\cdot 11+9,$$
so the digit \(10\) appears and
$$M_{11}(10)=19.$$
This is exactly the logic used by the interval branch.
The C++, Python, and Java implementations precompute the two exponents
$$\frac{p-1}{2}\qquad\text{and}\qquad\frac{p+1}{4},$$
together with \(p^2\). Then they loop through \(d=1,\dots,100000\), form the target digit \(a=p-d\), and use fast modular exponentiation to evaluate Euler's criterion.
If \(a\) is a quadratic residue, the implementation computes the modular square root by the closed form valid for primes \(p\equiv 3\pmod 4\), then takes the smaller of the two symmetric representatives.
If \(a\) is a non-residue, the implementation starts from the first interval lower bound \(p^2-dp\), repeatedly computes the ceiling integer square root of the current lower bound, and checks whether that square stays within the interval of width \(p\). If not, it shifts the interval upward by another \(p^2\) and repeats.
Each answer is added to a running total. Wide integer arithmetic is used where necessary so that values around \(p^2\) are handled safely.
Let \(D=100000\) be the number of queried digits. Each digit requires one modular exponentiation to test quadratic residuosity, and residue cases require one more modular exponentiation to recover a square root. Both operations cost \(O(\log p)\) modular multiplications.
In the non-residue case there is an additional interval loop. If \(T_d\) denotes the number of interval lifts needed for the digit \(p-d\), the total running time is
$$O\!\left(D\log p+\sum_{d=1}^{D} T_d\right).$$
The memory usage is \(O(1)\) beyond the storage needed for a few wide integers. For the fixed prime in the problem, this behaves essentially linearly in the number of digits being summed.
Die feste Primzahlbasis ist
$$p=10^9+7.$$
Für jedes \(d\in\{1,2,\dots,100000\}\) betrachtet die Implementierung die Ziffer
$$a=p-d,$$
also eine der \(100000\) größten von null verschiedenen Ziffern in Basis \(p\). Definiert wird
$$M_p(a)=\min\{m\ge 1:\text{in der Basis-}p\text{-Darstellung von }m^2\text{ kommt die Ziffer }a\text{ vor}\}.$$
Berechnet wird damit die Summe
$$\sum_{d=1}^{100000} M_p(p-d).$$
Eine direkte Suche ist unpraktikabel, weil das erste passende Quadrat bereits in der Größenordnung von \(p\) liegen kann. Deshalb wird die Ziffernbedingung in Kongruenzen und Intervallsuchen umformuliert.
Der zentrale Gedanke ist: Eine feste Ziffer in einer festen Basis entspricht einer Familie arithmetischer Intervalle. Für die speziellen Ziffern \(a=p-d\) bleiben am Ende nur zwei relevante Fälle übrig.
Die Ziffer \(a\) steht genau dann an Position \(k\ge 0\) in der Basis-\(p\)-Darstellung einer Zahl \(N\), wenn es ein \(t\ge 0\) gibt mit
$$a\,p^k+t\,p^{k+1}\le N\le a\,p^k+t\,p^{k+1}+p^k-1.$$
Für \(N=m^2\) bedeutet das: Jede mögliche Vorkommensstelle der Ziffer \(a\) in einem Quadrat entspricht der Frage, ob ein solches Intervall ein perfektes Quadrat enthält.
Für feste \(k\) und \(t\) ist der kleinste Kandidat immer
$$m=\left\lceil\sqrt{a\,p^k+t\,p^{k+1}}\right\rceil.$$
Das Problem reduziert sich also darauf, das erste Intervall zu finden, bei dem dieses aufgerundete Quadrat noch im selben Intervall liegt.
Hier ist \(a=p-d\) mit \(1\le d\le 100000\), also liegt \(a\) sehr nahe bei \(p\). Insbesondere gilt
$$a>\frac{p}{2}.$$
Steht \(a\) an der Einerstelle (\(k=0\)), genügt eine Kongruenz modulo \(p\).
Steht \(a\) an einer höheren Stelle (\(k\ge 1\)), dann folgt
$$m^2\ge a\,p>\frac{p^2}{2},$$
also
$$m>\frac{p}{\sqrt{2}}>\frac{p}{2}.$$
Eine Quadratwurzel modulo \(p\) kann dagegen immer durch eine positive Zahl höchstens \(p/2\) repräsentiert werden. Deshalb gilt:
Ist der Einerstellen-Fall möglich, liefert er automatisch das globale Minimum.
Ist er unmöglich, dann ist die kleinste verbleibende Stelle die \(p\)-Stelle (\(k=1\)); alle Stellen \(k\ge 2\) führen auf noch größere Werte.
Damit \(a\) die Endziffer von \(m^2\) ist, braucht man
$$m^2\equiv a \pmod p.$$
Das Euler-Kriterium entscheidet, ob diese Kongruenz lösbar ist:
$$a^{(p-1)/2}\equiv 1 \pmod p \iff a\text{ ist quadratischer Rest modulo }p.$$
Wegen
$$p\equiv 3\pmod 4$$
bekommt man eine Wurzel direkt durch
$$r\equiv a^{(p+1)/4}\pmod p.$$
Die beiden Lösungen modulo \(p\) sind \(r\) und \(p-r\), also ist die kleinste positive ganze Zahl mit Endziffer \(a\)
$$M_p(a)=\min(r,p-r).$$
Keine höhere Ziffernposition kann kleiner sein, weil jede solche Lösung bereits \(m>p/\sqrt2\) erfordert.
Ist \(a\) kein quadratischer Rest modulo \(p\), dann ist der Einerstellen-Fall ausgeschlossen. Die erste mögliche Stelle ist dann der Koeffizient von \(p\), also suchen wir Quadrate in Intervallen
$$I_t=[a\,p+t\,p^2,\ a\,p+t\,p^2+p-1]\qquad (t\ge 0).$$
Mit \(a=p-d\) wird die linke Grenze zu
$$L_t=a\,p+t\,p^2=p^2-dp+t\,p^2.$$
Für festes \(t\) ist der kleinste mögliche Kandidat
$$m_t=\left\lceil\sqrt{L_t}\right\rceil.$$
Genau dann liegt ein Quadrat im Intervall, wenn
$$m_t^2\le L_t+p-1.$$
Das erste \(t\), das diese Bedingung erfüllt, liefert das globale Minimum, weil die Intervalle streng ansteigen.
Ein kleines Rest-Beispiel ist Basis \(11\) mit Zielziffer \(9\). Es gilt
$$9\equiv 3^2\pmod{11},$$
also ist der kleinste positive Vertreter \(3\), und
$$3^2=9.$$
Damit ist \(M_{11}(9)=3\).
Ein kleines Nichtrest-Beispiel ist Basis \(11\) mit Zielziffer \(10\). Da \(10\) kein Quadrat modulo \(11\) ist, scheidet die Einerstelle aus. Man untersucht die Intervalle für die \(11\)-Stelle:
$$[110,120],\qquad [231,241],\qquad [352,362],\dots$$
Die aufgerundeten Quadratwurzeln der linken Grenzen sind
$$11,\qquad 16,\qquad 19.$$
Die ersten beiden Quadrate liegen außerhalb:
$$11^2=121>120,\qquad 16^2=256>241.$$
Das dritte passt:
$$19^2=361\in[352,362].$$
In Basis \(11\) schreibt sich das als
$$361=2\cdot 11^2+10\cdot 11+9,$$
also erscheint die Ziffer \(10\), und
$$M_{11}(10)=19.$$
Genau dieses Prinzip verwendet der Intervallzweig.
Die C++-, Python- und Java-Implementierungen berechnen zunächst die beiden Exponenten
$$\frac{p-1}{2}\qquad\text{und}\qquad\frac{p+1}{4},$$
sowie \(p^2\). Danach laufen sie über \(d=1,\dots,100000\), bilden die Zielziffer \(a=p-d\) und testen mit schneller modularer Potenzierung per Euler-Kriterium, ob \(a\) quadratischer Rest modulo \(p\) ist.
Im Rest-Fall wird mit der geschlossenen Formel für Primzahlen \(p\equiv 3\pmod 4\) eine modulare Quadratwurzel berechnet, anschließend wird der kleinere der beiden symmetrischen Vertreter gewählt.
Im Nichtrest-Fall startet die Implementierung bei der ersten Intervallgrenze \(p^2-dp\), berechnet jeweils die aufgerundete ganzzahlige Quadratwurzel und prüft, ob ihr Quadrat in einem Intervall der Breite \(p\) liegt. Falls nicht, wird die linke Grenze um \(p^2\) erhöht und der Test wiederholt.
Jeder gefundene Wert wird zu einer laufenden Summe addiert. Für Größenordnungen um \(p^2\) werden entsprechend breite Ganzzahltypen verwendet.
Sei \(D=100000\) die Anzahl der abgefragten Ziffern. Für jede Ziffer braucht man eine modulare Potenzierung zur Restklassifikation, und im Rest-Fall noch eine zweite zur Berechnung der Wurzel. Beides kostet \(O(\log p)\) modulare Multiplikationen.
Im Nichtrest-Fall kommt eine Intervallschleife hinzu. Bezeichnet \(T_d\) die Anzahl der benötigten Intervallverschiebungen für die Ziffer \(p-d\), dann ist die Gesamtlaufzeit
$$O\!\left(D\log p+\sum_{d=1}^{D} T_d\right).$$
Der Speicherbedarf ist \(O(1)\), abgesehen von wenigen breiten Ganzzahlen. Für die feste Primzahl des Problems verhält sich das Verfahren praktisch linear in der Anzahl der aufsummierten Ziffern.
Sabit asal taban
$$p=10^9+7$$
olarak alınır. Uygulama her \(d\in\{1,2,\dots,100000\}\) için şu rakamı inceler:
$$a=p-d.$$
Yani aslında taban \(p\) altında sıfır dışındaki en büyük \(100000\) rakam taranır. Tanım
$$M_p(a)=\min\{m\ge 1:\ m^2\text{ sayısının taban-}p\text{ yazımında }a\text{ rakamı geçer}\}$$
şeklindedir. Hesaplanan toplam da
$$\sum_{d=1}^{100000} M_p(p-d)$$
olur. Doğrudan arama gerçek boyutlarda mümkün değildir; çünkü ilk uygun kare kök değeri \(p\) mertebesine kadar çıkabilir. Bu yüzden çözüm, rakam koşulunu önce modüler bir teste, gerekirse de aralık taramasına dönüştürür.
Ana fikir şudur: taban gösterimindeki sabit bir rakam, sayılar doğrusu üzerinde belirli aralıklara karşılık gelir. Burada hedef rakamlar \(a=p-d\) olduğundan, sonunda sadece iki anlamlı durum kalır.
Bir \(N\) tam sayısının taban-\(p\) yazımında \(a\) rakamı \(k\ge 0\) konumunda bulunuyorsa ve ancak o zaman bir \(t\ge 0\) vardır ki
$$a\,p^k+t\,p^{k+1}\le N\le a\,p^k+t\,p^{k+1}+p^k-1.$$
\(N=m^2\) koyarsak, kare bir sayıda \(a\) rakamının görünmesi tam olarak bu tür bir aralığın bir tam kare içermesi anlamına gelir.
Sabit \(k\) ve \(t\) için mümkün olan en küçük aday
$$m=\left\lceil\sqrt{a\,p^k+t\,p^{k+1}}\right\rceil$$
olur. Dolayısıyla problem, yukarı yuvarlanan bu karekökün aynı aralığın içinde karesini veren ilk aralığı bulmaya indirgenir.
Burada \(a=p-d\) ve \(1\le d\le 100000\) olduğundan \(a\), \(p\)'ye çok yakındır. Özellikle
$$a>\frac{p}{2}.$$
Eğer \(a\) birler basamağında görünüyorsa (\(k=0\)), mesele yalnızca mod \(p\) altında bir karekök var mı sorusudur.
Eğer \(a\) daha üst bir basamakta görünüyorsa (\(k\ge 1\)), o zaman
$$m^2\ge a\,p>\frac{p^2}{2},$$
dolayısıyla
$$m>\frac{p}{\sqrt{2}}>\frac{p}{2}.$$
Öte yandan mod \(p\) altındaki bir karekök her zaman en fazla \(p/2\) olan pozitif bir temsilciyle yazılabilir. Bu yüzden:
Birler basamağı çözümü varsa, küresel minimum odur.
Birler basamağı çözümü yoksa, sonraki en küçük olasılık \(p\) katsayısındaki basamaktır (\(k=1\)); \(k\ge 2\) durumları daha da büyüktür.
\(a\) rakamının son basamakta görünmesi için gerekli ve yeterli koşul
$$m^2\equiv a \pmod p$$
olmasıdır. Euler ölçütü bu kongruansın çözülebilir olup olmadığını söyler:
$$a^{(p-1)/2}\equiv 1 \pmod p \iff a\text{, }p\text{ modunda kuadratik kalıntıdır.}$$
Ayrıca
$$p\equiv 3\pmod 4$$
olduğu için karekök doğrudan
$$r\equiv a^{(p+1)/4}\pmod p$$
ile bulunur. Mod \(p\) altındaki iki çözüm \(r\) ve \(p-r\) olduğundan, en küçük pozitif çözüm
$$M_p(a)=\min(r,p-r)$$
olur. Daha üst bir basamaktaki hiçbir çözüm bundan küçük olamaz; çünkü onlar zaten \(m>p/\sqrt2\) gerektirir.
Eğer \(a\), mod \(p\) altında kuadratik kalıntı değilse birler basamağı imkansızdır. O halde ilk mümkün yer \(p\) katsayısının bulunduğu basamaktır. Bu yüzden şu aralıkları tararız:
$$I_t=[a\,p+t\,p^2,\ a\,p+t\,p^2+p-1]\qquad (t\ge 0).$$
\(a=p-d\) yazınca sol uç
$$L_t=a\,p+t\,p^2=p^2-dp+t\,p^2$$
olur. Sabit \(t\) için en küçük aday
$$m_t=\left\lceil\sqrt{L_t}\right\rceil$$
şeklindedir. Aralık tam kare içerir ve ancak içerirse
$$m_t^2\le L_t+p-1$$
sağlanır. Bunu ilk sağlayan \(t\), artan aralıklar nedeniyle küresel minimumu verir.
Kalıntı dalı için küçük bir örnek, taban \(11\) ve hedef rakam \(9\)'dur. Çünkü
$$9\equiv 3^2\pmod{11},$$
en küçük pozitif temsilci \(3\) olur ve
$$3^2=9.$$
Dolayısıyla \(M_{11}(9)=3\).
Kalıntı olmayan dal için küçük bir örnek, taban \(11\) ve hedef rakam \(10\)'dur. \(10\), mod \(11\) altında kare olmadığı için birler basamağı imkansızdır. O zaman \(11\)'ler basamağı aralıklarına bakılır:
$$[110,120],\qquad [231,241],\qquad [352,362],\dots$$
Bu aralıkların sol uçlarının yukarı yuvarlanmış karekökleri
$$11,\qquad 16,\qquad 19$$
olur. İlk iki kare aralığı kaçırır:
$$11^2=121>120,\qquad 16^2=256>241.$$
Üçüncü kare uygundur:
$$19^2=361\in[352,362].$$
Ve taban \(11\)'de
$$361=2\cdot 11^2+10\cdot 11+9$$
olduğu için \(10\) rakamı görünür; yani
$$M_{11}(10)=19.$$
Aralık dalı tam olarak bu mantığı uygular.
C++, Python ve Java uygulamaları önce
$$\frac{p-1}{2}\qquad\text{ve}\qquad\frac{p+1}{4}$$
üslerini, ayrıca \(p^2\) değerini hazırlar. Sonra \(d=1,\dots,100000\) üzerinde dönüp hedef rakamı \(a=p-d\) olarak kurar ve hızlı modüler üs alma ile Euler ölçütünü hesaplar.
\(a\) bir kuadratik kalıntıysa, \(p\equiv 3\pmod 4\) için geçerli kapalı formülle modüler karekök bulunur ve iki simetrik temsilciden küçüğü seçilir.
\(a\) kalıntı değilse, algoritma \(p^2-dp\) alt sınırından başlar; mevcut alt sınırın tavan tam sayı karekökünü hesaplar; bu karenin genişliği \(p\) olan aralığın içine düşüp düşmediğini kontrol eder. Düşmüyorsa alt sınır bir kez daha \(p^2\) kadar artırılır ve işlem tekrarlanır.
Bulunan her değer toplam üzerine eklenir. \(p^2\) mertebesindeki büyüklükler için yeterince geniş tamsayı aritmetiği kullanılır.
\(D=100000\) sorgulanan rakam sayısı olsun. Her rakam için kuadratik kalıntı testinde bir modüler üs alma gerekir; kalıntı durumunda karekök için bir modüler üs alma daha yapılır. Bunların her biri \(O(\log p)\) maliyetlidir.
Kalıntı olmayan durumda ek olarak bir aralık döngüsü vardır. \(p-d\) rakamı için gereken aralık kaydırma sayısına \(T_d\) dersek toplam süre
$$O\!\left(D\log p+\sum_{d=1}^{D} T_d\right)$$
olur. Bellek kullanımı birkaç geniş tamsayı dışında \(O(1)\)'dir. Sorudaki sabit asal için yöntem, pratikte işlenen rakam sayısına göre yaklaşık lineer davranır.
La base prima fija es
$$p=10^9+7.$$
Para cada \(d\in\{1,2,\dots,100000\}\), la implementación estudia el dígito
$$a=p-d,$$
de modo que realmente recorre los \(100000\) mayores dígitos no nulos en base \(p\). Se define
$$M_p(a)=\min\{m\ge 1:\text{ la expansión en base }p\text{ de }m^2\text{ contiene el dígito }a\}.$$
La cantidad calculada es
$$\sum_{d=1}^{100000} M_p(p-d).$$
Una búsqueda directa sería inviable, porque el primer cuadrado válido puede aparecer ya en escala \(p\). Por eso la solución reemplaza la condición sobre dígitos por una mezcla de congruencias y búsquedas sobre intervalos.
La idea central es que fijar un dígito en una base fija equivale a fijar una familia de intervalos aritméticos. Para los dígitos especiales \(a=p-d\), esa observación deja solo dos casos verdaderamente relevantes.
Un dígito \(a\) aparece en la posición \(k\ge 0\) de la expansión en base \(p\) de un entero \(N\) si y solo si existe un entero \(t\ge 0\) tal que
$$a\,p^k+t\,p^{k+1}\le N\le a\,p^k+t\,p^{k+1}+p^k-1.$$
Tomando \(N=m^2\), cada posible aparición del dígito \(a\) dentro de un cuadrado equivale a preguntar si alguno de esos intervalos contiene un cuadrado perfecto.
Para \(k\) y \(t\) fijos, el menor candidato posible es
$$m=\left\lceil\sqrt{a\,p^k+t\,p^{k+1}}\right\rceil.$$
Así, el problema se reduce a encontrar el primer intervalo cuyo extremo inferior, al tomar la raíz cuadrada y redondear hacia arriba, siga produciendo un cuadrado dentro del mismo intervalo.
Aquí \(a=p-d\) con \(1\le d\le 100000\), luego \(a\) está muy cerca de \(p\) y en particular cumple
$$a>\frac{p}{2}.$$
Si \(a\) aparece en la unidad (\(k=0\)), basta una congruencia módulo \(p\).
Si \(a\) aparece en una posición superior (\(k\ge 1\)), entonces
$$m^2\ge a\,p>\frac{p^2}{2},$$
y por tanto
$$m>\frac{p}{\sqrt{2}}>\frac{p}{2}.$$
En cambio, una raíz cuadrada módulo \(p\) siempre puede representarse por un entero positivo no mayor que \(p/2\). De aquí se concluye:
Si el caso de la unidad es posible, ya da el mínimo global.
Si el caso de la unidad es imposible, la posición más pequeña restante es la del coeficiente de \(p\) (\(k=1\)); cualquier \(k\ge 2\) solo puede producir valores mayores.
Para que \(a\) sea el dígito final de \(m^2\), se necesita
$$m^2\equiv a \pmod p.$$
El criterio de Euler decide si esta congruencia tiene solución:
$$a^{(p-1)/2}\equiv 1 \pmod p \iff a\text{ es residuo cuadrático módulo }p.$$
Como además
$$p\equiv 3\pmod 4,$$
una raíz cuadrada se obtiene directamente mediante
$$r\equiv a^{(p+1)/4}\pmod p.$$
Las dos soluciones módulo \(p\) son \(r\) y \(p-r\), así que el menor entero positivo que hace aparecer el dígito \(a\) en la unidad es
$$M_p(a)=\min(r,p-r).$$
Ninguna aparición en una posición superior puede vencer a este valor, porque toda aparición superior ya exige \(m>p/\sqrt2\).
Si \(a\) no es residuo cuadrático módulo \(p\), la unidad queda descartada. La primera posición posible pasa a ser el coeficiente de \(p\), así que hay que buscar cuadrados en los intervalos
$$I_t=[a\,p+t\,p^2,\ a\,p+t\,p^2+p-1]\qquad (t\ge 0).$$
Como \(a=p-d\), el extremo izquierdo se escribe
$$L_t=a\,p+t\,p^2=p^2-dp+t\,p^2.$$
Para cada \(t\), el candidato mínimo es
$$m_t=\left\lceil\sqrt{L_t}\right\rceil.$$
El intervalo contiene un cuadrado exactamente cuando
$$m_t^2\le L_t+p-1.$$
El primer \(t\) que satisface esto da el mínimo global, porque los intervalos crecen estrictamente con \(t\).
Un ejemplo pequeño de la rama de residuo es base \(11\) con dígito objetivo \(9\). Se tiene
$$9\equiv 3^2\pmod{11},$$
por lo que el menor representante positivo es \(3\), y
$$3^2=9.$$
Así, \(M_{11}(9)=3\).
Un ejemplo pequeño de la rama no residual es base \(11\) con dígito objetivo \(10\). Como \(10\) no es cuadrado módulo \(11\), la unidad es imposible. Entonces se examinan los intervalos para la cifra en la posición de \(11\):
$$[110,120],\qquad [231,241],\qquad [352,362],\dots$$
Las raíces cuadradas enteras redondeadas hacia arriba son
$$11,\qquad 16,\qquad 19.$$
Los dos primeros cuadrados quedan fuera:
$$11^2=121>120,\qquad 16^2=256>241.$$
El tercero sí entra:
$$19^2=361\in[352,362].$$
En base \(11\), esto equivale a
$$361=2\cdot 11^2+10\cdot 11+9,$$
de modo que aparece el dígito \(10\) y
$$M_{11}(10)=19.$$
Ese es exactamente el mecanismo de la rama por intervalos.
Las implementaciones en C++, Python y Java precalculan los exponentes
$$\frac{p-1}{2}\qquad\text{y}\qquad\frac{p+1}{4},$$
junto con \(p^2\). Después recorren \(d=1,\dots,100000\), forman el dígito objetivo \(a=p-d\) y aplican exponenciación modular rápida para evaluar el criterio de Euler.
Si \(a\) es residuo cuadrático, la implementación recupera una raíz cuadrada modular mediante la fórmula cerrada válida para primos \(p\equiv 3\pmod 4\), y escoge el menor de los dos representantes simétricos.
Si \(a\) no es residuo, la implementación empieza en el extremo inferior \(p^2-dp\), calcula la raíz cuadrada entera por exceso de ese límite y comprueba si su cuadrado todavía cabe en el intervalo de anchura \(p\). Si no cabe, desplaza el intervalo sumando \(p^2\) y repite.
Cada respuesta se acumula en una suma total. Se usa aritmética entera suficientemente ancha para manipular con seguridad cantidades del orden de \(p^2\).
Sea \(D=100000\) el número de dígitos consultados. Cada dígito necesita una exponenciación modular para decidir si hay residuo cuadrático, y los casos residuales requieren una segunda exponenciación para recuperar una raíz. Ambas cuestan \(O(\log p)\) multiplicaciones modulares.
En la rama no residual aparece además un bucle de intervalos. Si \(T_d\) denota cuántos desplazamientos de intervalo hacen falta para el dígito \(p-d\), el tiempo total es
$$O\!\left(D\log p+\sum_{d=1}^{D} T_d\right).$$
La memoria utilizada es \(O(1)\), aparte de unos pocos enteros anchos. Para el primo fijo del problema, el comportamiento práctico es esencialmente lineal en el número de dígitos sumados.
固定的素数进制为
$$p=10^9+7.$$
对每个 \(d\in\{1,2,\dots,100000\}\)，实现实际考察的目标数字是
$$a=p-d.$$
也就是说，它遍历的是 base-\(p\) 下最大的 \(100000\) 个非零数字。定义
$$M_p(a)=\min\{m\ge 1:\ m^2\text{ 的 }p\text{ 进制表示中出现数字 }a\}.$$
最终求和的是
$$\sum_{d=1}^{100000} M_p(p-d).$$
直接枚举几乎没有可行性，因为第一个满足条件的平方根可能已经达到 \(p\) 的量级。实现因此不做暴力搜索，而是把“某个数字出现在平方数的 \(p\) 进制表示中”改写成同余判定与区间判定。
核心思想是：在固定进制里要求某个指定数字出现，等价于要求这个数落入一族结构非常规则的区间。对于这里的特殊目标数字 \(a=p-d\)，最终只需要处理两个分支。
若整数 \(N\) 的 \(p\) 进制表示中，数字 \(a\) 出现在第 \(k\ge 0\) 位，那么且仅那么存在某个整数 \(t\ge 0\)，使得
$$a\,p^k+t\,p^{k+1}\le N\le a\,p^k+t\,p^{k+1}+p^k-1.$$
把 \(N\) 换成 \(m^2\)，就得到：数字 \(a\) 出现在平方数 \(m^2\) 中，当且仅当某个这样的区间包含一个完全平方数。
对于固定的 \(k\) 与 \(t\)，最小的候选平方根一定是
$$m=\left\lceil\sqrt{a\,p^k+t\,p^{k+1}}\right\rceil.$$
所以问题转化为：找到第一个区间，使得它左端点的上取整平方根，其平方仍然没有跳出该区间。
这里的目标数字满足 \(a=p-d\)，而 \(1\le d\le 100000\)，因此 \(a\) 非常接近 \(p\)，特别地
$$a>\frac{p}{2}.$$
如果 \(a\) 出现在个位，也就是 \(k=0\)，那么问题只是“模 \(p\) 下是否有平方根”。
如果 \(a\) 出现在更高位，即 \(k\ge 1\)，那么一定有
$$m^2\ge a\,p>\frac{p^2}{2},$$
从而
$$m>\frac{p}{\sqrt{2}}>\frac{p}{2}.$$
另一方面，若模 \(p\) 的平方根存在，总能选到一个不超过 \(p/2\) 的正代表元。因此：
只要个位方案存在，它一定已经是全局最优。
如果个位方案不存在，那么最小的下一种可能只能是 \(k=1\)，也就是数字出现在 \(p\) 位；\(k\ge 2\) 会把 \(m\) 推得更大。
若要让 \(a\) 成为 \(m^2\) 的末位数字，就必须满足
$$m^2\equiv a \pmod p.$$
欧拉判别法告诉我们这个同余何时有解：
$$a^{(p-1)/2}\equiv 1 \pmod p \iff a\text{ 是模 }p\text{ 的二次剩余。}$$
而这里
$$p\equiv 3\pmod 4,$$
所以平方根可以直接写成
$$r\equiv a^{(p+1)/4}\pmod p.$$
模 \(p\) 的两个解是 \(r\) 与 \(p-r\)，因此最小的正整数解就是
$$M_p(a)=\min(r,p-r).$$
因为任何更高位的出现都已经要求 \(m>p/\sqrt2\)，所以这个值一旦存在，就必然已经是全局最小值。
如果 \(a\) 不是模 \(p\) 的二次剩余，那么个位方案不可能发生。此时最早可能出现的位置就是 \(p\) 位，于是要检查的区间是
$$I_t=[a\,p+t\,p^2,\ a\,p+t\,p^2+p-1]\qquad (t\ge 0).$$
代入 \(a=p-d\) 以后，左端点变成
$$L_t=a\,p+t\,p^2=p^2-dp+t\,p^2.$$
对每个固定的 \(t\)，最小候选值是
$$m_t=\left\lceil\sqrt{L_t}\right\rceil.$$
该区间包含平方数，当且仅当
$$m_t^2\le L_t+p-1.$$
因为这些区间随着 \(t\) 严格递增，所以第一个满足条件的 \(t\) 就给出全局最小的 \(m\)。
先看一个二次剩余的小例子：底数取 \(11\)，目标数字取 \(9\)。因为
$$9\equiv 3^2\pmod{11},$$
最小正代表元是 \(3\)，而且
$$3^2=9.$$
所以 \(M_{11}(9)=3\)。这对应“个位就能实现”的分支。
再看一个非剩余例子：底数仍取 \(11\)，目标数字改成 \(10\)。由于 \(10\) 不是模 \(11\) 的平方，个位不可能出现，于是只能检查 \(11\) 位对应的区间：
$$[110,120],\qquad [231,241],\qquad [352,362],\dots$$
这些区间左端点的上取整平方根分别为
$$11,\qquad 16,\qquad 19.$$
前两个都失败，因为
$$11^2=121>120,\qquad 16^2=256>241.$$
第三个成功：
$$19^2=361\in[352,362].$$
而
$$361=2\cdot 11^2+10\cdot 11+9,$$
说明 \(361\) 的 \(11\) 进制表示里确实出现了数字 \(10\)，因此
$$M_{11}(10)=19.$$
这正是实现中区间分支的工作方式。
C++、Python 和 Java 实现都会先准备好两个指数
$$\frac{p-1}{2}\qquad\text{和}\qquad\frac{p+1}{4},$$
以及 \(p^2\)。随后它们遍历 \(d=1,\dots,100000\)，构造目标数字 \(a=p-d\)，并通过快速模幂来计算欧拉判别。
如果 \(a\) 是二次剩余，实现就利用 \(p\equiv 3\pmod 4\) 时可直接写出的平方根公式求出模 \(p\) 的平方根，再在两个对称代表元中取较小者。
如果 \(a\) 不是二次剩余，实现就从第一个下界 \(p^2-dp\) 开始，计算当前下界的向上整数平方根，再检查其平方是否仍落在宽度为 \(p\) 的区间内。若没有落入，就把整个区间整体上移一个 \(p^2\) 再重复。
每次得到的最小值都会累加进总和。涉及 \(p^2\) 的地方会使用足够宽的整数类型，以避免溢出并保持判定准确。
设查询的数字个数为 \(D=100000\)。每个数字都需要一次模幂来判断是否为二次剩余；如果是剩余，还需要再做一次模幂来恢复平方根。这两步的代价都是 \(O(\log p)\)。
对非剩余情况，还会有一个区间上移循环。若记数字 \(p-d\) 所需的区间平移次数为 \(T_d\)，总时间复杂度为
$$O\!\left(D\log p+\sum_{d=1}^{D} T_d\right).$$
除少量大整数以外，空间复杂度是 \(O(1)\)。对于本题固定的素数，这个方法在实践中基本表现为对查询数字数量的线性增长。
Фиксированное простое основание равно
$$p=10^9+7.$$
Для каждого \(d\in\{1,2,\dots,100000\}\) реализация рассматривает цифру
$$a=p-d,$$
то есть фактически перебирает \(100000\) наибольших ненулевых цифр в системе счисления по основанию \(p\). Определяется функция
$$M_p(a)=\min\{m\ge 1:\text{ в записи }m^2\text{ по основанию }p\text{ встречается цифра }a\}.$$
Искомая сумма имеет вид
$$\sum_{d=1}^{100000} M_p(p-d).$$
Прямой перебор здесь бесполезен, потому что первое подходящее значение может быть уже порядка \(p\). Поэтому решение переводит условие о цифре в сочетание модульного теста и поиска по интервалам.
Главная идея такова: требование появления фиксированной цифры в фиксированном основании эквивалентно принадлежности числа одной из специальных арифметических полос. Для цифр вида \(a=p-d\) в итоге остаются только два существенных случая.
Цифра \(a\) стоит на позиции \(k\ge 0\) в записи числа \(N\) по основанию \(p\) тогда и только тогда, когда существует целое \(t\ge 0\) такое, что
$$a\,p^k+t\,p^{k+1}\le N\le a\,p^k+t\,p^{k+1}+p^k-1.$$
Подставляя \(N=m^2\), получаем: цифра \(a\) встречается в квадрате тогда и только тогда, когда некоторый такой интервал содержит полный квадрат.
При фиксированных \(k\) и \(t\) минимальный возможный кандидат равен
$$m=\left\lceil\sqrt{a\,p^k+t\,p^{k+1}}\right\rceil.$$
Значит, задача сводится к поиску первого интервала, для которого квадрат этого округленного вверх корня не выходит за правую границу того же интервала.
Здесь \(a=p-d\) и \(1\le d\le 100000\), то есть \(a\) очень близко к \(p\). В частности, выполнено
$$a>\frac{p}{2}.$$
Если цифра \(a\) появляется в младшем разряде (\(k=0\)), все сводится к сравнению по модулю \(p\).
Если же она стоит выше (\(k\ge 1\)), то обязательно
$$m^2\ge a\,p>\frac{p^2}{2},$$
а значит
$$m>\frac{p}{\sqrt{2}}>\frac{p}{2}.$$
С другой стороны, если квадратный корень по модулю \(p\) существует, его всегда можно выбрать как положительный представитель не больше \(p/2\). Отсюда сразу следует:
Если младший разряд возможен, он уже дает глобальный минимум.
Если младший разряд невозможен, минимальный оставшийся вариант — это позиция коэффициента при \(p\), то есть \(k=1\); случаи \(k\ge 2\) только увеличивают ответ.
Чтобы цифра \(a\) стала последней цифрой числа \(m^2\), нужно и достаточно, чтобы
$$m^2\equiv a \pmod p.$$
Критерий Эйлера решает вопрос существования решения:
$$a^{(p-1)/2}\equiv 1 \pmod p \iff a\text{ является квадратичным вычетом по модулю }p.$$
Поскольку
$$p\equiv 3\pmod 4,$$
квадратный корень можно выписать явно:
$$r\equiv a^{(p+1)/4}\pmod p.$$
Два решения по модулю \(p\) — это \(r\) и \(p-r\), поэтому минимальное положительное целое равно
$$M_p(a)=\min(r,p-r).$$
Никакое появление цифры на более старшей позиции не может дать меньший \(m\), потому что там уже требуется \(m>p/\sqrt2\).
Если \(a\) не является квадратичным вычетом по модулю \(p\), младший разряд невозможен. Тогда первая возможная позиция — это коэффициент при \(p\), и нужно искать квадраты в интервалах
$$I_t=[a\,p+t\,p^2,\ a\,p+t\,p^2+p-1]\qquad (t\ge 0).$$
Так как \(a=p-d\), левый конец равен
$$L_t=a\,p+t\,p^2=p^2-dp+t\,p^2.$$
Для каждого \(t\) минимальный кандидат имеет вид
$$m_t=\left\lceil\sqrt{L_t}\right\rceil.$$
Интервал содержит квадрат тогда и только тогда, когда
$$m_t^2\le L_t+p-1.$$
Первое подходящее \(t\) дает глобальный минимум, потому что интервалы строго возрастают.
Небольшой пример для ветви вычета: основание \(11\), целевая цифра \(9\). Имеем
$$9\equiv 3^2\pmod{11},$$
поэтому минимальный положительный представитель равен \(3\), и
$$3^2=9.$$
Следовательно, \(M_{11}(9)=3\).
Небольшой пример для ветви невычета: основание \(11\), целевая цифра \(10\). Число \(10\) не является квадратом по модулю \(11\), поэтому младший разряд невозможен. Тогда рассматриваются интервалы для позиции при \(11\):
$$[110,120],\qquad [231,241],\qquad [352,362],\dots$$
Соответствующие округленные вверх квадратные корни равны
$$11,\qquad 16,\qquad 19.$$
Первые два квадрата не попадают в свои интервалы:
$$11^2=121>120,\qquad 16^2=256>241.$$
Третий попадает:
$$19^2=361\in[352,362].$$
А в системе по основанию \(11\)
$$361=2\cdot 11^2+10\cdot 11+9,$$
то есть цифра \(10\) действительно появляется, и
$$M_{11}(10)=19.$$
Именно так работает интервальная ветвь алгоритма.
Реализации на C++, Python и Java заранее вычисляют показатели
$$\frac{p-1}{2}\qquad\text{и}\qquad\frac{p+1}{4},$$
а также значение \(p^2\). Затем они перебирают \(d=1,\dots,100000\), строят целевую цифру \(a=p-d\) и с помощью быстрого возведения в степень по модулю проверяют критерий Эйлера.
Если \(a\) — квадратичный вычет, реализация находит модульный квадратный корень по замкнутой формуле, корректной для простых \(p\equiv 3\pmod 4\), после чего выбирает меньший из двух симметричных представителей.
Если \(a\) — невычет, реализация начинает с нижней границы \(p^2-dp\), вычисляет целочисленный квадратный корень с округлением вверх и проверяет, остается ли его квадрат внутри интервала ширины \(p\). Если нет, интервал сдвигается вверх на \(p^2\), и проверка повторяется.
Каждое найденное значение прибавляется к общей сумме. Для величин порядка \(p^2\) используются достаточно широкие целочисленные типы.
Пусть \(D=100000\) — число запрашиваемых цифр. Для каждой цифры нужна одна модульная степень, чтобы определить, является ли она квадратичным вычетом, и в случае вычета еще одна степень, чтобы восстановить корень. Обе операции стоят \(O(\log p)\) модульных умножений.
В ветви невычета добавляется цикл по интервалам. Если через \(T_d\) обозначить число сдвигов интервала, требуемых для цифры \(p-d\), то общее время работы равно
$$O\!\left(D\log p+\sum_{d=1}^{D} T_d\right).$$
Память равна \(O(1)\), не считая нескольких широких целых чисел. Для фиксированного простого числа из задачи метод на практике ведет себя почти линейно по количеству суммируемых цифр.
الأساس الأولي الثابت هو
$$p=10^9+7.$$
ولكل \(d\in\{1,2,\dots,100000\}\) فإن التطبيق يدرس الرقم
$$a=p-d.$$
أي إنه في الحقيقة يبحث بين أكبر \(100000\) رقم غير صفري في الأساس \(p\). ونعرّف الدالة التالية:
$$M_p(a)=\min\{m\ge 1:\ a\text{ appears in the base-}p\text{ expansion of }m^2\}.$$
وعليه فإن الكمية المحسوبة هي
$$\sum_{d=1}^{100000} M_p(p-d).$$
البحث المباشر غير عملي، لأن أول جذر تربيعي صالح قد يكون بحجم يقارب \(p\). لذلك يحول الحل شرط ظهور الرقم إلى اختبار توافقات بترديد \(p\)، وإن فشل ذلك ينتقل إلى فحص نوافذ عددية محددة.
الفكرة الأساسية هي أن ظهور رقم محدد في أساس محدد يعادل وقوع العدد داخل عائلة من الفترات الحسابية. وبالنسبة للأرقام الخاصة \(a=p-d\)، لا يبقى في النهاية إلا حالتان فعليتان.
يظهر الرقم \(a\) في الموضع \(k\ge 0\) من كتابة عدد صحيح \(N\) بالأساس \(p\) إذا وفقط إذا وُجد عدد صحيح \(t\ge 0\) يحقق
$$a\,p^k+t\,p^{k+1}\le N\le a\,p^k+t\,p^{k+1}+p^k-1.$$
وعند وضع \(N=m^2\) يصبح معنى ذلك أن ظهور الرقم \(a\) داخل مربع كامل يكافئ تمامًا احتواء إحدى هذه الفترات على مربع كامل.
ولكل \(k\) و\(t\) ثابتين فإن أصغر مرشح ممكن هو
$$m=\left\lceil\sqrt{a\,p^k+t\,p^{k+1}}\right\rceil.$$
إذن المسألة تختزل إلى العثور على أول فترة يكون فيها مربع هذا الجذر المدوّر إلى الأعلى ما زال داخل الفترة نفسها.
لدينا هنا \(a=p-d\) مع \(1\le d\le 100000\)، ولذلك فإن \(a\) قريب جدًا من \(p\)، وبالأخص
$$a>\frac{p}{2}.$$
إذا ظهر \(a\) في خانة الآحاد (\(k=0\)) فالمسألة كلها تصبح وجود جذر تربيعي بترديد \(p\).
أما إذا ظهر في خانة أعلى (\(k\ge 1\)) فلا بد أن
$$m^2\ge a\,p>\frac{p^2}{2},$$
ومن ثم
$$m>\frac{p}{\sqrt{2}}>\frac{p}{2}.$$
في المقابل، إذا وُجد جذر تربيعي بترديد \(p\) فيمكن دائمًا اختياره على صورة ممثل موجب لا يتجاوز \(p/2\). ولهذا:
إذا كانت حالة الآحاد ممكنة فهي تعطي الحل الأصغر عالميًا مباشرة.
وإذا كانت مستحيلة، فإن أصغر موضع متبقٍ هو خانة معامل \(p\) أي \(k=1\)، أما المواضع \(k\ge 2\) فلا يمكن إلا أن تنتج قيمًا أكبر.
كي يكون \(a\) هو الرقم الأخير في \(m^2\)، يجب أن يتحقق
$$m^2\equiv a \pmod p.$$
ويحسم معيار أويلر وجود حل لهذه المطابقة. وتكون النتيجة المعيارية الأساسية
$$a^{(p-1)/2}\equiv 1 \pmod p.$$
وهذا يكافئ كون \(a\) بقايا تربيعية بترديد \(p\).
وبما أن
$$p\equiv 3\pmod 4,$$
فإن الجذر التربيعي يعطى مباشرةً بالعلاقة
$$r\equiv a^{(p+1)/4}\pmod p.$$
والحلّان بترديد \(p\) هما \(r\) و\(p-r\)، لذلك يكون أصغر ممثل موجب هو
$$M_p(a)=\min(r,p-r).$$
ولا يمكن لأي ظهور في خانة أعلى أن يكون أصغر، لأن كل ظهور أعلى يتطلب أصلًا \(m>p/\sqrt2\).
إذا لم يكن \(a\) بقايا تربيعية بترديد \(p\)، فإن خانة الآحاد مستحيلة. وعندها يكون أول موضع ممكن هو خانة معامل \(p\)، فنبحث عن مربعات داخل الفترات
$$I_t=[a\,p+t\,p^2,\ a\,p+t\,p^2+p-1]\qquad (t\ge 0).$$
وبالتعويض \(a=p-d\) يصبح الطرف الأيسر
$$L_t=a\,p+t\,p^2=p^2-dp+t\,p^2.$$
ولكل \(t\) فإن أصغر مرشح ممكن هو
$$m_t=\left\lceil\sqrt{L_t}\right\rceil.$$
وتحتوي الفترة مربعًا كاملًا إذا وفقط إذا تحقق
$$m_t^2\le L_t+p-1.$$
وأول قيمة \(t\) تحقق هذا الشرط تعطي الحل الأدنى عالميًا، لأن هذه الفترات تصعد تصاعدًا صارمًا مع \(t\).
مثال صغير على فرع الباقي التربيعي: في الأساس \(11\) ومع الرقم الهدف \(9\)، لدينا
$$9\equiv 3^2\pmod{11},$$
إذًا أصغر ممثل موجب هو \(3\)، كما أن
$$3^2=9.$$
ومن ثم \(M_{11}(9)=3\).
ومثال صغير على فرع اللاباقي: في الأساس \(11\) ومع الرقم الهدف \(10\)، فإن \(10\) ليس مربعًا بترديد \(11\)، لذا لا يمكن أن يظهر في خانة الآحاد. ننتقل إذن إلى فترات خانة \(11\):
$$[110,120],\qquad [231,241],\qquad [352,362],\dots$$
وجذور الحدود اليسرى بعد التقريب إلى الأعلى هي
$$11,\qquad 16,\qquad 19.$$
الأولان يفشلان لأن
$$11^2=121>120,\qquad 16^2=256>241.$$
أما الثالث فينجح:
$$19^2=361\in[352,362].$$
وفي الأساس \(11\) نكتب
$$361=2\cdot 11^2+10\cdot 11+9,$$
ولذلك يظهر الرقم \(10\) فعلًا، ويكون
$$M_{11}(10)=19.$$
وهذا هو عين منطق فرع البحث على الفترات.
تقوم تطبيقات C++ وPython وJava أولًا بتجهيز الأسّين
$$\frac{p-1}{2},\qquad\frac{p+1}{4}.$$
إضافة إلى \(p^2\). ثم تدور على \(d=1,\dots,100000\)، وتبني الرقم الهدف \(a=p-d\)، وتستخدم الأسّ المعياري السريع لتطبيق معيار أويلر.
إذا كان \(a\) بقايا تربيعية، تحسب الشيفرة الجذر التربيعي بترديد \(p\) بواسطة الصيغة المغلقة الصالحة عندما \(p\equiv 3\pmod 4\)، ثم تختار الأصغر بين الممثلين المتناظرين.
وإذا لم يكن \(a\) بقايا تربيعية، تبدأ الشيفرة من الحد الأدنى \(p^2-dp\)، وتحسب الجذر التربيعي الصحيح مع التقريب إلى الأعلى، ثم تختبر هل يبقى مربعه داخل الفترة ذات العرض \(p\). وإذا لم يبقَ، ترفع الفترة بمقدار \(p^2\) وتكرر العملية.
كل قيمة دنيا يتم إيجادها تضاف إلى المجموع الكلي. وتُستخدم أنواع أعداد صحيحة واسعة بما يكفي للتعامل الآمن مع قيم من مرتبة \(p^2\).
ليكن \(D=100000\) هو عدد الأرقام المطلوبة. كل رقم يحتاج إلى عملية أسّ معياري واحدة لاختبار كونه بقايا تربيعية، وتحتاج حالات الباقي التربيعي إلى عملية أسّ معياري ثانية لاستخراج الجذر. وكل من هاتين العمليتين تكلف \(O(\log p)\) ضربات معيارية.
في فرع اللاباقي توجد حلقة إضافية على الفترات. وإذا رمزنا بعدد مرات رفع الفترة اللازمة للرقم \(p-d\) بالرمز \(T_d\)، فإن الزمن الكلي يساوي
$$O\!\left(D\log p+\sum_{d=1}^{D} T_d\right).$$
أما الذاكرة فهي \(O(1)\) عدا عدد قليل من القيم الصحيحة الواسعة. ومع الأساس الأولي الثابت في المسألة، يكون السلوك العملي قريبًا جدًا من الخطي في عدد الأرقام المجمعة.