Start with the list \(2,3,\dots,n\). Each operation finds the smallest current entry and replaces it by its square. After \(m\) operations we need the sum of all entries modulo \(1234567891\). Because \(m\) can be enormous, the solution does not simulate every step on the raw integers.
For each initial base \(b\in\{2,\dots,n\}\), let \(t_b\) be the number of times that entry has been selected so far. Its current value is then
$$b^{2^{t_b}}.$$
The solution separates two tasks: determining which entry is currently smallest, and evaluating the final values modulo the prime modulus.
The logarithm is strictly increasing, so comparing values is equivalent to comparing their logarithms. For the entry that started at \(b\), define
$$\lambda_b=\log\left(b^{2^{t_b}}\right)=2^{t_b}\log b.$$
Choosing the smallest current number is therefore the same as choosing the smallest \(\lambda_b\). One squaring sends
$$\lambda_b \longmapsto 2\lambda_b.$$
This lets the implementation maintain a min-priority structure on logarithmic keys instead of on astronomically large integers. When two logarithmic keys are equal, the values are equal as well; the implementations use a deterministic secondary order so the data structure stays stable.
Write the ordered logarithms at some moment as
$$\lambda_1\le \lambda_2\le \cdots \le \lambda_L,\qquad L=n-1.$$
Suppose the smallest one satisfies
$$2\lambda_1\le \lambda_L.$$
After squaring that smallest entry, its new logarithm is still no larger than the current maximum. So it may remain among the small values and can affect the immediate future ordering in a nontrivial way. During this phase the algorithm performs exact heap updates one operation at a time.
The number of such explicit updates is usually far smaller than \(m\), because each update doubles one logarithm and quickly pushes that entry upward.
The explicit phase stops once
$$2\lambda_1>\lambda_L.$$
Now squaring the smallest entry sends it strictly past every untouched entry, because its new logarithm exceeds the current maximum. One step therefore transforms the sorted list into
$$\lambda_2,\lambda_3,\dots,\lambda_L,2\lambda_1.$$
The relative order of the untouched entries does not change, and the updated entry moves to the end. Repeating the same argument shows that the next selected entry must be \(\lambda_2\), then \(\lambda_3\), and so on. After one full round of \(L\) operations, every entry has been squared exactly once and the ordered list becomes
$$2\lambda_1,2\lambda_2,\dots,2\lambda_L.$$
The key point is that the same inequality still holds after scaling the entire list by \(2\):
$$2(2\lambda_1)>2\lambda_L \iff 2\lambda_1>\lambda_L.$$
So once this regime begins, the process continues in identical cycles forever.
Let \(r_{\mathrm{rem}}\) be the number of operations left after the explicit phase. Since the balanced regime proceeds in complete rounds over the \(L\) entries, write
$$r_{\mathrm{rem}}=qL+s,\qquad 0\le s<L.$$
Then every entry is squared \(q\) more times, and the first \(s\) entries in the current sorted logarithmic order are squared once additional time. Equivalently, if the balanced-order list is
$$\lambda_1\le \lambda_2\le \cdots \le \lambda_L,$$
then entries \(1,2,\dots,s\) receive \(q+1\) further squarings, while entries \(s+1,\dots,L\) receive \(q\). This replaces an astronomically large tail of the process by one division and one remainder.
If the current residue modulo \(M=1234567891\) is \(v\), then applying \(t\) further squarings produces
$$v^{2^t}\pmod{M}.$$
Therefore the bulk phase only needs the exponents \(2^q\) and \(2^{q+1}\). Because \(M\) is prime and the initial bases \(2,3,\dots,n\) are all nonzero modulo \(M\), every later residue is also nonzero modulo \(M\). Fermat's little theorem therefore reduces exponents modulo \(M-1\):
$$a^k\equiv a^{\,k\bmod (M-1)}\pmod{M}\qquad (a\not\equiv 0\pmod{M}).$$
So the implementation computes \(2^q\bmod (M-1)\), doubles it to obtain \(2^{q+1}\bmod (M-1)\), and then evaluates the required modular powers for the final sum.
The initial list is \(2,3,4,5\). The first three operations are easy to follow directly:
$$[2,3,4,5]\to [4,3,4,5]\to [4,9,4,5]\to [16,9,4,5].$$
Therefore the required sum is
$$16+9+4+5=34,$$
which matches the checkpoint used by the implementations.
To see the bulk rule in isolation, suppose the ordered logarithms after the explicit phase are \(1.40,1.55,1.80,2.10\). Since \(2\cdot 1.40=2.80>2.10\), the next four selections are forced to occur in that same order. If seven operations remain, then
$$7=1\cdot 4+3,$$
so every entry is squared once more, and the first three receive one extra squaring.
The C++, Python, and Java implementations store two pieces of information for each entry: a logarithmic key used only for ordering, and the current residue modulo \(1234567891\). They initialize a min-priority structure with the values \(2,3,\dots,n\) and also track the largest current logarithm.
While doubling the smallest logarithm does not jump beyond the current maximum, the implementation performs one exact update: remove the minimum, double its logarithmic key, square its residue modulo the prime, reinsert it, and refresh the current maximum if needed.
Once the balanced inequality \(2\lambda_{\min}>\lambda_{\max}\) holds, the remaining items are extracted and sorted by the same ordering rule. The implementation then computes the quotient \(q\) and remainder \(s\) of the remaining step count by \(L=n-1\), converts those counts into the exponents \(2^q\) and \(2^{q+1}\) modulo \(M-1\), and applies fast modular exponentiation to each stored residue. The first \(s\) sorted entries receive the larger exponent, the rest receive the smaller one, and the resulting residues are summed modulo \(M\).
Let \(L=n-1\), and let \(u\) be the number of explicit priority-queue updates performed before the balanced regime begins. The implementations insert \(L\) initial items into the priority structure, which costs \(O(L\log L)\). The explicit phase then costs \(O(u\log L)\), because each update removes and reinserts one element.
After that, the remaining work is one sort of \(L\) items, one exponentiation to compute \(2^q\bmod(M-1)\), and \(L\) modular exponentiations for the final residues. This gives overall running time
$$O(u\log L+L\log L+L\log M+\log q),$$
which simplifies to \(O(u\log L+L\log L)\) when the modulus is treated as fixed. The memory usage is \(O(L)\). The important point is that the method avoids any linear dependence on the huge value of \(m\) after the short explicit phase.
Wir starten mit der Liste \(2,3,\dots,n\). In jeder Operation wird der aktuell kleinste Eintrag ausgewählt und durch sein Quadrat ersetzt. Nach \(m\) Operationen ist die Summe aller Einträge modulo \(1234567891\) gesucht. Da \(m\) extrem groß sein kann, simuliert die Lösung nicht jeden Schritt auf den tatsächlichen riesigen Zahlen.
Für jeden Startwert \(b\in\{2,\dots,n\}\) sei \(t_b\) die Anzahl der bisherigen Auswahlen dieses Eintrags. Sein aktueller Wert ist dann
$$b^{2^{t_b}}.$$
Die Lösung trennt zwei Aufgaben: erstens die Frage, welcher Eintrag aktuell der kleinste ist, und zweitens die Berechnung der Endwerte modulo des Primmoduls.
Der Logarithmus ist streng monoton, also ist der Vergleich der Werte gleichbedeutend mit dem Vergleich ihrer Logarithmen. Für den Eintrag mit Startwert \(b\) definieren wir
$$\lambda_b=\log\left(b^{2^{t_b}}\right)=2^{t_b}\log b.$$
Den aktuell kleinsten Wert zu wählen ist damit genau dasselbe wie den kleinsten \(\lambda_b\) zu wählen. Eine Quadrierung bewirkt
$$\lambda_b \longmapsto 2\lambda_b.$$
So kann die Implementierung eine Min-Prioritätsstruktur auf logarithmischen Schlüsseln pflegen, anstatt mit astronomisch großen Ganzzahlen zu arbeiten. Falls zwei Schlüssel gleich sind, sind auch die Werte gleich; die Implementierungen verwenden dann eine feste sekundäre Ordnung, damit die Datenstruktur deterministisch bleibt.
Seien die geordneten Logarithmen zu einem bestimmten Zeitpunkt
$$\lambda_1\le \lambda_2\le \cdots \le \lambda_L,\qquad L=n-1.$$
Gilt für den kleinsten Wert
$$2\lambda_1\le \lambda_L,$$
dann bleibt sein neuer Logarithmus nach dem Quadrieren höchstens so groß wie das bisherige Maximum. Der Eintrag kann also weiterhin in der Nähe des Minimums liegen und die nächste Auswahl kompliziert beeinflussen. In dieser Phase führt der Algorithmus deshalb jede Heap-Aktualisierung exakt Schritt für Schritt aus.
Die Zahl dieser expliziten Schritte ist meist deutlich kleiner als \(m\), weil jede Aktualisierung genau einen Logarithmus verdoppelt und den betreffenden Eintrag schnell nach oben schiebt.
Die explizite Phase endet, sobald
$$2\lambda_1>\lambda_L$$
gilt. Dann springt der kleinste Eintrag nach dem Quadrieren strikt über alle unberührten Einträge hinaus, denn sein neuer Logarithmus ist größer als das aktuelle Maximum. Ein Schritt verwandelt die sortierte Liste also in
$$\lambda_2,\lambda_3,\dots,\lambda_L,2\lambda_1.$$
Die relative Ordnung der unberührten Einträge bleibt erhalten, und der aktualisierte Eintrag wandert ans Ende. Dieselbe Überlegung zeigt, dass anschließend \(\lambda_2\) gewählt wird, dann \(\lambda_3\) und so weiter. Nach einer vollständigen Runde aus \(L\) Operationen wurde jeder Eintrag genau einmal quadriert, und die sortierte Liste lautet
$$2\lambda_1,2\lambda_2,\dots,2\lambda_L.$$
Wichtig ist, dass die entscheidende Ungleichung unter dieser globalen Skalierung erhalten bleibt:
$$2(2\lambda_1)>2\lambda_L \iff 2\lambda_1>\lambda_L.$$
Sobald dieses Regime also erreicht ist, läuft der Prozess in identischen Zyklen weiter.
Sei \(r_{\mathrm{rem}}\) die Anzahl der nach der expliziten Phase noch verbleibenden Operationen. Da das balancierte Regime aus vollständigen Runden über die \(L\) Einträge besteht, schreiben wir
$$r_{\mathrm{rem}}=qL+s,\qquad 0\le s<L.$$
Dann wird jeder Eintrag noch \(q\)-mal quadriert, und die ersten \(s\) Einträge in der aktuellen sortierten Logarithmusordnung werden ein weiteres Mal quadriert. Anders gesagt: Für
$$\lambda_1\le \lambda_2\le \cdots \le \lambda_L$$
erhalten die Einträge \(1,2,\dots,s\) insgesamt \(q+1\) weitere Quadrierungen, während die Einträge \(s+1,\dots,L\) genau \(q\) weitere Quadrierungen erhalten. So wird ein riesiger Rest des Prozesses auf eine Division und einen Rest reduziert.
Ist der aktuelle Rest modulo \(M=1234567891\) gleich \(v\), dann führen \(t\) weitere Quadrierungen zu
$$v^{2^t}\pmod{M}.$$
Für die Sammelphase werden also nur die Exponenten \(2^q\) und \(2^{q+1}\) benötigt. Da \(M\) prim ist und die Startwerte \(2,3,\dots,n\) alle ungleich \(0\) modulo \(M\) sind, bleiben auch alle späteren Reste von \(0\) verschieden. Mit dem kleinen Satz von Fermat dürfen die Exponenten deshalb modulo \(M-1\) reduziert werden:
$$a^k\equiv a^{\,k\bmod (M-1)}\pmod{M}\qquad (a\not\equiv 0\pmod{M}).$$
Die Implementierung berechnet also \(2^q\bmod (M-1)\), verdoppelt diesen Wert zu \(2^{q+1}\bmod (M-1)\) und wertet damit die benötigten modularen Potenzen für die Endsumme aus.
Die Startliste ist \(2,3,4,5\). Die ersten drei Operationen lassen sich direkt verfolgen:
$$[2,3,4,5]\to [4,3,4,5]\to [4,9,4,5]\to [16,9,4,5].$$
Damit ist die gesuchte Summe
$$16+9+4+5=34,$$
genau der Kontrollwert der Implementierungen.
Zur Illustration der Sammelregel nehmen wir symbolisch an, dass die sortierten Logarithmen nach der expliziten Phase \(1.40,1.55,1.80,2.10\) sind. Weil \(2\cdot 1.40=2.80>2.10\), sind die nächsten vier Auswahlen zwingend in genau dieser Reihenfolge. Bleiben noch sieben Operationen, also
$$7=1\cdot 4+3,$$
dann wird jeder Eintrag noch einmal quadriert, und die ersten drei erhalten eine zusätzliche Quadrierung.
Die C++-, Python- und Java-Implementierungen speichern zu jedem Eintrag zwei Informationen: einen logarithmischen Schlüssel nur für die Ordnung und den aktuellen Rest modulo \(1234567891\). Danach initialisieren sie eine Min-Prioritätsstruktur mit den Werten \(2,3,\dots,n\) und halten zusätzlich den aktuell größten Logarithmus fest.
Solange das Verdoppeln des kleinsten Logarithmus nicht über das aktuelle Maximum hinausspringt, führt die Implementierung ein exaktes Update aus: Minimum entfernen, logarithmischen Schlüssel verdoppeln, den gespeicherten Rest modulo der Primzahl quadrieren, wieder einfügen und gegebenenfalls das Maximum aktualisieren.
Sobald die balancierte Ungleichung \(2\lambda_{\min}>\lambda_{\max}\) gilt, werden die verbleibenden Einträge entnommen und nach derselben Regel sortiert. Anschließend berechnet die Implementierung den Quotienten \(q\) und den Rest \(s\) der verbleibenden Schrittzahl durch \(L=n-1\), wandelt diese in die Exponenten \(2^q\) und \(2^{q+1}\) modulo \(M-1\) um und verwendet schnelle modulare Exponentiation auf den gespeicherten Resten. Die ersten \(s\) sortierten Einträge erhalten den größeren Exponenten, die übrigen den kleineren, und zum Schluss werden alle Beiträge modulo \(M\) addiert.
Sei \(L=n-1\), und sei \(u\) die Anzahl der expliziten Aktualisierungen vor Beginn des balancierten Regimes. Die Implementierungen fügen zunächst \(L\) Elemente in die Prioritätsstruktur ein, was \(O(L\log L)\) kostet. Die explizite Phase kostet danach \(O(u\log L)\), weil jede Aktualisierung genau ein Entfernen und ein erneutes Einfügen umfasst.
Anschließend bleiben eine Sortierung von \(L\) Elementen, eine Exponentiation zur Berechnung von \(2^q\bmod(M-1)\) und \(L\) modulare Potenzberechnungen für die Endreste. Insgesamt ergibt sich damit die Laufzeit
$$O(u\log L+L\log L+L\log M+\log q),$$
was sich bei festem Modul zu \(O(u\log L+L\log L)\) vereinfacht. Der Speicherverbrauch beträgt \(O(L)\). Entscheidend ist, dass nach der kurzen expliziten Phase keine lineare Abhängigkeit mehr von dem riesigen \(m\) besteht.
Başlangıç listesi \(2,3,\dots,n\) şeklindedir. Her işlemde o andaki en küçük eleman seçilir ve karesi alınır. \(m\) işlem sonunda tüm elemanların toplamı \(1234567891\) modunda istenir. \(m\) çok büyük olabildiği için çözüm, gerçek sayıların tamamını adım adım simüle etmez.
Her başlangıç tabanı \(b\in\{2,\dots,n\}\) için, bu elemanın şimdiye kadar kaç kez seçildiğini \(t_b\) ile gösterelim. O andaki değeri
$$b^{2^{t_b}}$$
olur. Çözüm iki işi birbirinden ayırır: hangi elemanın şu anda en küçük olduğunu bulmak ve son değerleri asal modül altında hesaplamak.
Logaritma fonksiyonu sıkı artandır; dolayısıyla değerleri karşılaştırmak ile logaritmalarını karşılaştırmak aynıdır. Başlangıçta \(b\) olan eleman için
$$\lambda_b=\log\left(b^{2^{t_b}}\right)=2^{t_b}\log b$$
tanımını yapalım. Böylece en küçük güncel sayıyı seçmek, en küçük \(\lambda_b\) değerini seçmekle tamamen aynı hale gelir. Bir kez daha kare almak
$$\lambda_b \longmapsto 2\lambda_b$$
dönüşümünü yapar. Bu sayede uygulama, astronomik büyüklükteki tamsayıları saklamak yerine logaritmik anahtarlar üzerinde bir min-öncelik yapısı kullanabilir. İki logaritmik anahtar eşitse gerçek değerler de eşittir; uygulamalar veri yapısını kararlı tutmak için sabit bir ikinci sıralama kullanır.
Bir anda sıralı logaritmalar
$$\lambda_1\le \lambda_2\le \cdots \le \lambda_L,\qquad L=n-1$$
olsun. Eğer en küçüğü için
$$2\lambda_1\le \lambda_L$$
sağlanıyorsa, bu eleman kare alındıktan sonra bile yeni logaritması mevcut maksimumu geçmez. Yani küçükler grubunda kalabilir ve bir sonraki seçimleri karmaşık biçimde etkileyebilir. Bu aşamada algoritma her işlemi öncelik kuyruğu üzerinde tam olarak tek tek uygular.
Bu açık güncellemelerin sayısı genellikle \(m\)'den çok küçüktür; çünkü her güncelleme bir logaritmayı iki katına çıkarır ve o elemanı hızla yukarı taşır.
Açık simülasyon şu anda durur:
$$2\lambda_1>\lambda_L.$$
Artık en küçük eleman kare alındığında yeni logaritması mevcut maksimumdan büyük olur; yani dokunulmamış bütün elemanların üstüne sıçrar. Bu yüzden tek bir adım sıralı listeyi
$$\lambda_2,\lambda_3,\dots,\lambda_L,2\lambda_1$$
şekline dönüştürür. Dokunulmayan elemanların kendi iç sırası değişmez, güncellenen eleman da sona gider. Aynı akıl yürütme bir sonraki seçimin \(\lambda_2\), sonra \(\lambda_3\) ve bu şekilde devam edeceğini gösterir. \(L\) işlemlik tam bir turun sonunda her eleman tam bir kez kare alınmış olur ve sıralı liste
$$2\lambda_1,2\lambda_2,\dots,2\lambda_L$$
haline gelir. Kritik nokta, belirleyici eşitsizliğin bu ortak ölçekleme altında da korunmasıdır:
$$2(2\lambda_1)>2\lambda_L \iff 2\lambda_1>\lambda_L.$$
Dolayısıyla bu rejime girildiğinde süreç artık aynı döngülerle sonsuza kadar sürer.
Açık faz bittikten sonra kalan işlem sayısı \(r_{\mathrm{rem}}\) olsun. Dengelenmiş rejim \(L\) eleman üzerinde tam turlar halinde ilerlediği için
$$r_{\mathrm{rem}}=qL+s,\qquad 0\le s<L$$
yazarız. Böylece her eleman \(q\) kez daha kare alınır; mevcut sıralı logaritma düzenindeki ilk \(s\) eleman ise bir kez daha ekstra kare alınır. Başka bir deyişle
$$\lambda_1\le \lambda_2\le \cdots \le \lambda_L$$
düzeninde \(1,2,\dots,s\) elemanları toplam \(q+1\) ek kare alma, \(s+1,\dots,L\) elemanları ise \(q\) ek kare alma alır. Böylece çok büyük bir kuyruk, tek bir bölüm ve kalan hesabına indirgenir.
Modül \(M=1234567891\) altında mevcut kalan \(v\) ise, \(t\) adet ek kare alma sonucu
$$v^{2^t}\pmod{M}$$
elde edilir. Demek ki toplu faz için yalnızca \(2^q\) ve \(2^{q+1}\) üsleri gerekir. \(M\) asal olduğundan ve başlangıç tabanları \(2,3,\dots,n\) mod \(M\) altında sıfır olmadığından, sonraki tüm kalanlar da sıfır olmayan kalırlar. Bu nedenle Fermat'nın küçük teoremi ile üsler \(M-1\) moduna indirilebilir:
$$a^k\equiv a^{\,k\bmod (M-1)}\pmod{M}\qquad (a\not\equiv 0\pmod{M}).$$
Uygulama bu yüzden \(2^q\bmod(M-1)\) değerini hesaplar, bunu ikiyle çarparak \(2^{q+1}\bmod(M-1)\) elde eder ve son toplam için gereken modüler üsleri bunlarla hesaplar.
Başlangıç listesi \(2,3,4,5\) olur. İlk üç adım doğrudan izlenebilir:
$$[2,3,4,5]\to [4,3,4,5]\to [4,9,4,5]\to [16,9,4,5].$$
Dolayısıyla istenen toplam
$$16+9+4+5=34$$
olur; bu da uygulamalardaki kontrol değeriyle aynıdır.
Toplu kuralı ayrıca sembolik olarak görmek için, açık faz sonrası sıralı logaritmaların \(1.40,1.55,1.80,2.10\) olduğunu düşünelim. Çünkü \(2\cdot 1.40=2.80>2.10\), sonraki dört seçim zorunlu olarak bu sırada gerçekleşir. Eğer yedi işlem kalmışsa
$$7=1\cdot 4+3,$$
yani her eleman bir kez daha kare alınır ve ilk üçü bir ek kare alma daha alır.
C++, Python ve Java uygulamaları her eleman için iki bilgi tutar: yalnızca sıralama için kullanılan logaritmik bir anahtar ve \(1234567891\) modundaki mevcut kalan. Ardından \(2,3,\dots,n\) değerleriyle bir min-öncelik yapısı başlatılır ve ayrıca o andaki en büyük logaritma izlenir.
En küçük logaritmayı ikiyle çarpmak mevcut maksimumun üstüne sıçramadığı sürece uygulama bir tam güncelleme yapar: minimumu çıkarır, logaritmik anahtarı iki katına çıkarır, modüler kalanı asal mod altında karesine yükseltir, tekrar ekler ve gerekirse maksimumu günceller.
Dengelenmiş eşitsizlik \(2\lambda_{\min}>\lambda_{\max}\) sağlandığında kalan elemanlar çıkarılıp aynı kuralla sıralanır. Sonra uygulama kalan adım sayısını \(L=n-1\)'e bölerek bölüm \(q\) ve kalan \(s\) değerlerini bulur, bunları \(M-1\) modunda \(2^q\) ve \(2^{q+1}\) üslerine çevirir ve saklanan kalıntılar üzerinde hızlı modüler üs alma uygular. Sıralı ilk \(s\) eleman büyük üssü, geri kalanlar küçük üssü alır; son olarak tüm katkılar \(M\) modunda toplanır.
\(L=n-1\) ve dengelenmiş rejime geçmeden önce yapılan açık öncelik kuyruğu güncelleme sayısı \(u\) olsun. Uygulamalar başlangıçta \(L\) elemanı öncelik yapısına ekler; bunun maliyeti \(O(L\log L)\)'dir. Açık faz ise her güncellemede bir çıkarma ve bir ekleme yaptığı için \(O(u\log L)\) zaman alır.
Bundan sonra \(L\) elemanın bir kez sıralanması, \(2^q\bmod(M-1)\) için bir üs hesabı ve son kalıntılar için \(L\) adet modüler üs alma kalır. Toplam çalışma süresi
$$O(u\log L+L\log L+L\log M+\log q)$$
olur; modül sabit kabul edildiğinde bu \(O(u\log L+L\log L)\)'ye iner. Bellek kullanımı \(O(L)\)'dir. Esas kazanç, kısa açık fazdan sonra algoritmanın artık devasa \(m\) ile doğrusal şekilde büyümemesidir.
Se comienza con la lista \(2,3,\dots,n\). En cada operación se toma el menor valor actual y se sustituye por su cuadrado. Tras \(m\) operaciones hay que calcular la suma de todos los elementos módulo \(1234567891\). Como \(m\) puede ser gigantesco, la solución no simula todos los pasos sobre los enteros reales, que crecerían demasiado.
Para cada base inicial \(b\in\{2,\dots,n\}\), sea \(t_b\) el número de veces que esa entrada ha sido elegida hasta el momento. Su valor actual es
$$b^{2^{t_b}}.$$
La idea central es separar dos tareas: decidir qué entrada es actualmente la menor y calcular los valores finales módulo el primo dado.
El logaritmo es estrictamente creciente, así que comparar valores equivale a comparar sus logaritmos. Para la entrada que empezó en \(b\), definimos
$$\lambda_b=\log\left(b^{2^{t_b}}\right)=2^{t_b}\log b.$$
Elegir el menor número actual equivale entonces a elegir el menor \(\lambda_b\). Una operación de cuadrado transforma
$$\lambda_b \longmapsto 2\lambda_b.$$
Esto permite mantener una estructura de prioridad mínima sobre claves logarítmicas en lugar de sobre enteros astronómicos. Si dos claves coinciden, los valores también coinciden; las implementaciones usan un criterio secundario determinista para mantener estable la estructura.
Escribamos los logaritmos ordenados en cierto instante como
$$\lambda_1\le \lambda_2\le \cdots \le \lambda_L,\qquad L=n-1.$$
Si el menor cumple
$$2\lambda_1\le \lambda_L,$$
entonces, después de elevarlo al cuadrado, su nuevo logaritmo todavía no supera al máximo actual. Por tanto, puede seguir estando entre los valores pequeños y afectar de forma no trivial al orden de los siguientes pasos. En esta fase el algoritmo realiza actualizaciones exactas de la cola de prioridad, una por una.
El número de estas actualizaciones explícitas suele ser muy inferior a \(m\), porque cada una duplica un logaritmo y empuja rápidamente esa entrada hacia arriba.
La fase explícita termina cuando
$$2\lambda_1>\lambda_L.$$
Desde ese momento, al cuadrar la entrada mínima su nuevo logaritmo queda estrictamente por encima de todas las entradas no tocadas, ya que supera al máximo actual. Un paso transforma entonces la lista ordenada en
$$\lambda_2,\lambda_3,\dots,\lambda_L,2\lambda_1.$$
El orden relativo de las \(L-1\) entradas no modificadas no cambia, y la entrada actualizada pasa al final. Repitiendo el mismo razonamiento se ve que la siguiente elegida será \(\lambda_2\), luego \(\lambda_3\), y así sucesivamente. Tras una ronda completa de \(L\) operaciones, cada entrada ha sido elevada al cuadrado exactamente una vez y la lista ordenada se convierte en
$$2\lambda_1,2\lambda_2,\dots,2\lambda_L.$$
Además, la desigualdad decisiva se conserva al multiplicar toda la lista por \(2\):
$$2(2\lambda_1)>2\lambda_L \iff 2\lambda_1>\lambda_L.$$
Por eso, una vez alcanzado este régimen, el proceso continúa en ciclos idénticos.
Sea \(r_{\mathrm{rem}}\) el número de operaciones que quedan tras la fase explícita. Como el régimen equilibrado avanza en rondas completas sobre las \(L\) entradas, escribimos
$$r_{\mathrm{rem}}=qL+s,\qquad 0\le s<L.$$
Entonces cada entrada recibe \(q\) cuadrados adicionales, y las primeras \(s\) entradas en el orden logarítmico actual reciben uno más. Equivalente a decir: si en ese instante
$$\lambda_1\le \lambda_2\le \cdots \le \lambda_L,$$
entonces las entradas \(1,2,\dots,s\) reciben \(q+1\) cuadrados adicionales, mientras que las entradas \(s+1,\dots,L\) reciben \(q\). Así, una cola enorme del proceso se resume en una división y un resto.
Si el residuo actual módulo \(M=1234567891\) es \(v\), entonces aplicar \(t\) cuadrados más produce
$$v^{2^t}\pmod{M}.$$
Por tanto, la fase masiva sólo necesita los exponentes \(2^q\) y \(2^{q+1}\). Como \(M\) es primo y las bases iniciales \(2,3,\dots,n\) son todas no nulas módulo \(M\), todos los residuos posteriores siguen siendo no nulos. El pequeño teorema de Fermat permite entonces reducir los exponentes módulo \(M-1\):
$$a^k\equiv a^{\,k\bmod (M-1)}\pmod{M}\qquad (a\not\equiv 0\pmod{M}).$$
La implementación calcula \(2^q\bmod(M-1)\), lo duplica para obtener \(2^{q+1}\bmod(M-1)\) y usa esos exponentes en las potencias modulares finales.
La lista inicial es \(2,3,4,5\). Los tres primeros pasos se siguen de forma directa:
$$[2,3,4,5]\to [4,3,4,5]\to [4,9,4,5]\to [16,9,4,5].$$
Así, la suma pedida es
$$16+9+4+5=34,$$
que coincide con el punto de control usado por las implementaciones.
Para ver la regla masiva por separado, supongamos que tras la fase explícita los logaritmos ordenados son \(1.40,1.55,1.80,2.10\). Como \(2\cdot 1.40=2.80>2.10\), las cuatro selecciones siguientes quedan forzadas en ese mismo orden. Si quedan siete operaciones, entonces
$$7=1\cdot 4+3,$$
de modo que cada entrada recibe un cuadrado adicional y las tres primeras reciben uno más.
Las implementaciones en C++, Python y Java guardan dos datos por entrada: una clave logarítmica usada sólo para ordenar y el residuo actual módulo \(1234567891\). Después inicializan una estructura de prioridad mínima con los valores \(2,3,\dots,n\) y mantienen también el mayor logaritmo actual.
Mientras duplicar el menor logaritmo no lo haga saltar por encima del máximo actual, la implementación hace una actualización exacta: extrae el mínimo, duplica su clave logarítmica, eleva al cuadrado su residuo módulo el primo, lo vuelve a insertar y actualiza el máximo si hace falta.
Una vez que se cumple la desigualdad equilibrada \(2\lambda_{\min}>\lambda_{\max}\), los elementos restantes se extraen y se ordenan con la misma regla. Luego la implementación calcula el cociente \(q\) y el resto \(s\) al dividir los pasos pendientes entre \(L=n-1\), convierte esos conteos en los exponentes \(2^q\) y \(2^{q+1}\) módulo \(M-1\), y aplica exponenciación modular rápida a cada residuo almacenado. Las primeras \(s\) entradas ordenadas reciben el exponente mayor, las demás el menor, y finalmente todos los residuos se suman módulo \(M\).
Sea \(L=n-1\), y sea \(u\) el número de actualizaciones explícitas de la cola de prioridad antes de entrar en el régimen equilibrado. Las implementaciones insertan primero \(L\) elementos en la estructura, lo que cuesta \(O(L\log L)\). La fase explícita cuesta \(O(u\log L)\), ya que cada actualización hace una extracción y una reinserción.
Después sólo queda una ordenación de \(L\) elementos, una exponenciación para calcular \(2^q\bmod(M-1)\) y \(L\) potencias modulares para los residuos finales. El tiempo total es
$$O(u\log L+L\log L+L\log M+\log q),$$
que se simplifica a \(O(u\log L+L\log L)\) si el módulo se considera fijo. El uso de memoria es \(O(L)\). Lo esencial es que, tras la corta fase explícita, el método evita cualquier dependencia lineal en el enorme valor de \(m\).
初始列表为 \(2,3,\dots,n\)。每一步都找出当前最小的数，并把它替换成它的平方。执行完 \(m\) 次操作后，需要求所有元素之和对 \(1234567891\) 取模的结果。由于 \(m\) 可以非常大，解法不能按真实整数逐步模拟到最后。
对每个初始底数 \(b\in\{2,\dots,n\}\)，记 \(t_b\) 为它到当前时刻被选中的次数。那么它此时的真实值就是
$$b^{2^{t_b}}.$$
整个思路把问题拆成两部分：一部分只负责判断“现在谁最小”，另一部分只负责在模素数意义下恢复最终数值。
因为对数函数严格递增，所以比较两个正数的大小，与比较它们对数的大小完全等价。对于起始值为 \(b\) 的那一项，定义
$$\lambda_b=\log\left(b^{2^{t_b}}\right)=2^{t_b}\log b.$$
于是，“找出当前最小值”就变成了“找出最小的 \(\lambda_b\)”。如果某个元素再被平方一次，那么它的对数会变成
$$\lambda_b \longmapsto 2\lambda_b.$$
这一步非常关键，因为真实数值会很快增长到无法直接存储，而对数键只需要做比较和翻倍。若两个对数键相等，对应的真实值也相等；实现中会再使用一个固定的次序规则，使优先队列的行为保持确定。
设某一时刻排好序的对数为
$$\lambda_1\le \lambda_2\le \cdots \le \lambda_L,\qquad L=n-1.$$
如果当前最小者满足
$$2\lambda_1\le \lambda_L,$$
那么它被平方以后，新的对数仍然不会超过当前最大对数。这意味着它仍然可能留在“较小的一群”里，接下来谁会最先被选中并不呈现简单的轮转结构。因此在这一阶段，算法必须老老实实地做精确模拟：取出最小者，把它的对数翻倍，把它的模值平方，再放回优先队列。
不过这部分通常并不会很长，因为每做一次更新，就有一个元素的对数直接翻倍，很快就会被推到较大的区域里去。
精确模拟停止的条件是
$$2\lambda_1>\lambda_L.$$
一旦这个不等式成立，最小元素再被平方时，它的新对数就会严格大于当前最大对数。也就是说，它会一下子跳到所有未更新元素的后面。于是一次操作之后，排好序的列表必定变成
$$\lambda_2,\lambda_3,\dots,\lambda_L,2\lambda_1.$$
这里有两个重要结论。第一，剩余那 \(L-1\) 个没有被动过的元素，它们之间的相对顺序完全不变。第二，刚刚更新的那个元素一定移到最后面。因此下一次被选中的一定是原来的 \(\lambda_2\)，再下一次一定是原来的 \(\lambda_3\)，依此类推。
经过整整一轮 \(L\) 次操作之后，每个元素都会恰好再被平方一次，此时排好序的对数列表就是
$$2\lambda_1,2\lambda_2,\dots,2\lambda_L.$$
更重要的是，决定进入这一轮转结构的关键不等式在整体乘以 \(2\) 后仍然成立：
$$2(2\lambda_1)>2\lambda_L \iff 2\lambda_1>\lambda_L.$$
所以只要进入这个区间，之后的过程就会一轮一轮地重复同样的模式，不再需要逐步模拟每一次选择。
设精确阶段结束后还剩下 \(r_{\mathrm{rem}}\) 次操作。由于此时系统按长度为 \(L\) 的完整轮次前进，我们可以写成
$$r_{\mathrm{rem}}=qL+s,\qquad 0\le s<L.$$
这表示：每个元素都会再被平方 \(q\) 次，而按当前对数顺序排在最前面的 \(s\) 个元素还会多平方一次。也就是说，如果当前平衡状态下的顺序是
$$\lambda_1\le \lambda_2\le \cdots \le \lambda_L,$$
那么编号 \(1,2,\dots,s\) 的元素共得到 \(q+1\) 次额外平方，编号 \(s+1,\dots,L\) 的元素共得到 \(q\) 次额外平方。这样一来，原本可能极其巨大的剩余过程就被压缩成一次整除和一次取余。
如果某个元素当前在模 \(M=1234567891\) 下的余数是 \(v\)，那么再平方 \(t\) 次以后，它的模值就是
$$v^{2^t}\pmod{M}.$$
因此，批处理阶段真正需要的只是不同比例的两个指数：\(2^q\) 和 \(2^{q+1}\)。由于 \(M\) 是素数，而初始底数 \(2,3,\dots,n\) 都不被 \(M\) 整除，所以它们在模 \(M\) 下都非零；非零数不断平方以后仍然非零。于是可以使用费马小定理把指数按 \(M-1\) 缩减：
$$a^k\equiv a^{\,k\bmod (M-1)}\pmod{M}\qquad (a\not\equiv 0\pmod{M}).$$
实现先计算 \(2^q\bmod(M-1)\)，再把它乘以 \(2\) 得到 \(2^{q+1}\bmod(M-1)\)，最后对每个保存下来的模值做快速模幂并求和。
初始列表是 \(2,3,4,5\)。前三次操作可以直接写出来：
$$[2,3,4,5]\to [4,3,4,5]\to [4,9,4,5]\to [16,9,4,5].$$
因此最终要求的和为
$$16+9+4+5=34,$$
这与实现中使用的检验值一致。
如果只想看批量分配规则，可以假设精确阶段结束后，对数顺序为 \(1.40,1.55,1.80,2.10\)。因为 \(2\cdot 1.40=2.80>2.10\)，接下来的四次选择必然按这个顺序轮流发生。若此时还剩七步，那么
$$7=1\cdot 4+3,$$
表示每个元素至少再平方一次，而前面三个元素还会额外再平方一次。
C++、Python 和 Java 实现都会为每个元素保存两份信息：一份是只用于比较大小的对数键，另一份是当前对 \(1234567891\) 取模后的余数。初始化时，把 \(2,3,\dots,n\) 全部放入一个最小优先结构中，并同时维护当前最大的对数值。
只要把最小对数翻倍后还没有超过当前最大对数，实现就执行一次精确更新：取出最小项，把它的对数乘以 \(2\)，把它的模余数平方，再放回结构中，并在必要时刷新最大对数。
一旦满足平衡不等式 \(2\lambda_{\min}>\lambda_{\max}\)，剩余元素就会被全部取出，并按相同的比较规则排序。随后实现把剩余步数除以 \(L=n-1\)，得到商 \(q\) 与余数 \(s\)，再把它们转换成模 \(M-1\) 的指数 \(2^q\) 与 \(2^{q+1}\)，然后对每个已保存的余数执行快速模幂。排序后前 \(s\) 个元素使用较大的指数，其余元素使用较小的指数，最后把所有结果在模 \(M\) 下相加。
令 \(L=n-1\)，再令 \(u\) 为进入平衡区间之前执行的显式优先队列更新次数。实现首先向优先结构中插入 \(L\) 个元素，这一步代价为 \(O(L\log L)\)。显式阶段每次更新都包含一次取出和一次放回，因此总代价为 \(O(u\log L)\)。
之后还需要做一次长度为 \(L\) 的排序、一次计算 \(2^q\bmod(M-1)\) 的快速幂，以及 \(L\) 次最终模幂。总时间复杂度为
$$O(u\log L+L\log L+L\log M+\log q),$$
当模数视为固定常数时，可简化为 \(O(u\log L+L\log L)\)。空间复杂度为 \(O(L)\)。真正的加速点在于：在短暂的显式阶段之后，算法不再与巨大的 \(m\) 成线性关系。
Исходный набор состоит из чисел \(2,3,\dots,n\). На каждом шаге выбирается текущее минимальное число и заменяется своим квадратом. После \(m\) операций нужно найти сумму всех элементов по модулю \(1234567891\). Поскольку \(m\) может быть огромным, решение не выполняет полную пошаговую симуляцию на самих гигантских числах.
Для каждого исходного основания \(b\in\{2,\dots,n\}\) обозначим через \(t_b\) число раз, когда этот элемент уже выбирался. Тогда его текущее значение равно
$$b^{2^{t_b}}.$$
Ключевая идея состоит в том, чтобы отделить задачу сравнения текущих величин от задачи вычисления итоговых значений по модулю простого числа.
Логарифм строго возрастает, поэтому сравнение положительных чисел эквивалентно сравнению их логарифмов. Для элемента, стартовавшего из \(b\), введём
$$\lambda_b=\log\left(b^{2^{t_b}}\right)=2^{t_b}\log b.$$
Тогда выбор текущего минимума сводится к выбору минимального \(\lambda_b\). Одна операция возведения в квадрат переводит
$$\lambda_b \longmapsto 2\lambda_b.$$
Это позволяет хранить в структуре приоритета не сами огромные числа, а только логарифмические ключи. Если два ключа совпадают, то совпадают и реальные значения; для устойчивого поведения структуры реализации используют детерминированный вторичный порядок.
Пусть в некоторый момент упорядоченные логарифмы равны
$$\lambda_1\le \lambda_2\le \cdots \le \lambda_L,\qquad L=n-1.$$
Если для минимального элемента выполнено
$$2\lambda_1\le \lambda_L,$$
то после возведения в квадрат его новый логарифм всё ещё не превосходит текущего максимума. Значит, этот элемент может остаться среди сравнительно малых и нетривиально влиять на ближайший порядок выборов. В этой зоне алгоритм делает точные обновления структуры приоритета по одному шагу.
Обычно число таких явных обновлений намного меньше \(m\), потому что каждое обновление удваивает один логарифм и быстро уводит соответствующий элемент вверх.
Явная фаза заканчивается, когда выполняется
$$2\lambda_1>\lambda_L.$$
После этого, если возвести в квадрат минимальный элемент, его новый логарифм окажется строго больше текущего максимума. Следовательно, за один шаг упорядоченный список переходит в
$$\lambda_2,\lambda_3,\dots,\lambda_L,2\lambda_1.$$
Относительный порядок нетронутых элементов сохраняется, а обновлённый элемент уходит в конец. Из того же рассуждения следует, что дальше будут выбраны \(\lambda_2\), затем \(\lambda_3\), и так далее. После полной серии из \(L\) операций каждый элемент будет возведён в квадрат ровно один раз, а список станет равен
$$2\lambda_1,2\lambda_2,\dots,2\lambda_L.$$
Решающая деталь состоит в том, что ключевое неравенство сохраняется и после умножения всего списка на \(2\):
$$2(2\lambda_1)>2\lambda_L \iff 2\lambda_1>\lambda_L.$$
Значит, как только этот режим достигнут, процесс дальше идёт по одинаковым циклам.
Пусть после явной фазы остаётся \(r_{\mathrm{rem}}\) операций. В сбалансированном режиме процесс идёт полными раундами по \(L\) элементам, поэтому пишем
$$r_{\mathrm{rem}}=qL+s,\qquad 0\le s<L.$$
Это означает, что каждый элемент будет дополнительно возведён в квадрат \(q\) раз, а первые \(s\) элементов в текущем порядке логарифмов получат ещё по одному дополнительному возведению в квадрат. Иначе говоря, если сейчас
$$\lambda_1\le \lambda_2\le \cdots \le \lambda_L,$$
то элементы \(1,2,\dots,s\) получают \(q+1\) дальнейших квадратов, а элементы \(s+1,\dots,L\) получают \(q\). Так огромный хвост процесса сводится к одному делению и одному остатку.
Если текущий остаток по модулю \(M=1234567891\) равен \(v\), то после ещё \(t\) возведений в квадрат получится
$$v^{2^t}\pmod{M}.$$
Следовательно, в пакетной фазе нужны только показатели \(2^q\) и \(2^{q+1}\). Поскольку \(M\) простое, а исходные основания \(2,3,\dots,n\) не делятся на \(M\), все последующие остатки также остаются ненулевыми по модулю \(M\). Поэтому по малой теореме Ферма показатель можно уменьшать по модулю \(M-1\):
$$a^k\equiv a^{\,k\bmod (M-1)}\pmod{M}\qquad (a\not\equiv 0\pmod{M}).$$
Реализация вычисляет \(2^q\bmod(M-1)\), удваивает это значение для получения \(2^{q+1}\bmod(M-1)\), а затем использует быстрые модульные степени для суммирования окончательных вкладов.
Начальный список имеет вид \(2,3,4,5\). Первые три операции легко выписать явно:
$$[2,3,4,5]\to [4,3,4,5]\to [4,9,4,5]\to [16,9,4,5].$$
Поэтому искомая сумма равна
$$16+9+4+5=34,$$
и это совпадает с контрольным значением, используемым в реализациях.
Чтобы отдельно увидеть правило пакетного распределения, можно предположить, что после явной фазы упорядоченные логарифмы равны \(1.40,1.55,1.80,2.10\). Так как \(2\cdot 1.40=2.80>2.10\), следующие четыре выбора уже принудительно происходят именно в этом порядке. Если осталось семь операций, то
$$7=1\cdot 4+3,$$
то есть каждый элемент будет возведён в квадрат ещё один раз, а первые три получат ещё по одному дополнительному возведению.
Реализации на C++, Python и Java хранят для каждого элемента две характеристики: логарифмический ключ, нужный только для упорядочивания, и текущий остаток по модулю \(1234567891\). Затем они инициализируют минимальную структуру приоритета значениями \(2,3,\dots,n\) и параллельно отслеживают наибольший текущий логарифм.
Пока удвоение минимального логарифма не перебрасывает его выше текущего максимума, реализация делает точное обновление: извлекает минимум, удваивает его логарифмический ключ, возводит сохранённый остаток в квадрат по модулю простого числа, вставляет элемент обратно и при необходимости обновляет максимум.
Когда начинает выполняться неравенство \(2\lambda_{\min}>\lambda_{\max}\), все оставшиеся элементы извлекаются и сортируются по тому же правилу. Далее реализация находит частное \(q\) и остаток \(s\) от деления оставшегося числа шагов на \(L=n-1\), переводит их в показатели \(2^q\) и \(2^{q+1}\) по модулю \(M-1\) и применяет быстрые модульные степени к каждому сохранённому остатку. Первые \(s\) элементов в отсортированном порядке получают больший показатель, остальные меньший, после чего все вклады суммируются по модулю \(M\).
Пусть \(L=n-1\), а \(u\) обозначает число явных обновлений структуры приоритета до входа в сбалансированный режим. Сначала реализации вставляют \(L\) элементов в структуру, что стоит \(O(L\log L)\). Явная фаза затем требует \(O(u\log L)\), потому что каждое обновление состоит из одного извлечения и одной повторной вставки.
После этого остаются одна сортировка \(L\) элементов, одно быстрое возведение для вычисления \(2^q\bmod(M-1)\) и \(L\) модульных степеней для конечных остатков. Итого время работы равно
$$O(u\log L+L\log L+L\log M+\log q),$$
что упрощается до \(O(u\log L+L\log L)\), если модуль считать фиксированным. Память составляет \(O(L)\). Главная выгода состоит в том, что после короткой явной фазы алгоритм уже не зависит линейно от огромного \(m\).
نبدأ بالقائمة \(2,3,\dots,n\). في كل عملية نختار أصغر عنصر حالي ونستبدله بمربعه. بعد تنفيذ \(m\) عملية نريد مجموع جميع العناصر بترديد \(1234567891\). وبما أن \(m\) قد يكون هائلاً جداً، فلا يمكن الاعتماد على محاكاة كاملة خطوة بخطوة على القيم الصحيحة نفسها.
لكل قيمة ابتدائية \(b\in\{2,\dots,n\}\)، لنرمز بـ \(t_b\) إلى عدد المرات التي تم فيها اختيار ذلك العنصر حتى اللحظة الحالية. عندئذ تكون قيمته الراهنة
$$b^{2^{t_b}}.$$
الفكرة الأساسية هي فصل مهمتين مختلفتين: معرفة أي عنصر هو الأصغر الآن، وحساب القيمة النهائية لكل عنصر بترديد العدد الأولي المعطى.
بما أن دالة اللوغاريتم متزايدة تماماً، فإن مقارنة القيم الموجبة تكافئ تماماً مقارنة لوغاريتماتها. للعنصر الذي بدأ من \(b\)، نعرّف
$$\lambda_b=\log\left(b^{2^{t_b}}\right)=2^{t_b}\log b.$$
عندها يصبح اختيار أصغر قيمة حالية هو نفسه اختيار أصغر \(\lambda_b\). وإذا رُبِّع العنصر مرة إضافية فإن لوغاريتمه يتحول إلى
$$\lambda_b \longmapsto 2\lambda_b.$$
وهذا مهم جداً لأن القيم الحقيقية تنمو بسرعة هائلة، بينما يكفي في الترتيب أن نحتفظ بمفاتيح لوغاريتمية ونجري عليها المقارنات والتضعيف. وإذا تساوت قيمتان لوغاريتميتان فالقيم الحقيقية متساوية أيضاً؛ لذلك تستخدم التطبيقات ترتيباً ثانوياً ثابتاً للحفاظ على سلوك حتمي داخل بنية الأولوية.
لنكتب اللوغاريتمات المرتبة في لحظة ما على الصورة
$$\lambda_1\le \lambda_2\le \cdots \le \lambda_L,\qquad L=n-1.$$
إذا تحقق للعنصر الأصغر أن
$$2\lambda_1\le \lambda_L,$$
فإن لوغاريتمه بعد التربيع لا يزال لا يتجاوز أكبر لوغاريتم حالي. وهذا يعني أنه قد يبقى بين العناصر الصغيرة نسبياً، وبالتالي قد يؤثر ترتيب الخطوات التالية بطريقة غير بسيطة. في هذه المرحلة ينفذ الخوارزم تحديثات دقيقة على بنية الأولوية، عمليةً واحدةً في كل مرة.
وغالباً ما يكون عدد هذه التحديثات الصريحة أصغر بكثير من \(m\)، لأن كل تحديث يضاعف أحد اللوغاريتمات ويدفع ذلك العنصر سريعاً نحو القيم الكبيرة.
تنتهي المرحلة الصريحة عندما يصبح
$$2\lambda_1>\lambda_L.$$
من هذه اللحظة، إذا رُبِّع العنصر الأصغر فإن لوغاريتمه الجديد يصبح أكبر من أكبر لوغاريتم حالي، أي إنه يقفز مباشرةً إلى ما بعد جميع العناصر التي لم تُحدَّث. لذلك تتحول القائمة المرتبة بعد خطوة واحدة إلى
$$\lambda_2,\lambda_3,\dots,\lambda_L,2\lambda_1.$$
يبقى الترتيب النسبي للعناصر غير الممسوسة كما هو، بينما ينتقل العنصر المحدَّث إلى النهاية. ومن الحجة نفسها نستنتج أن العنصر التالي المختار سيكون \(\lambda_2\)، ثم \(\lambda_3\)، وهكذا دواليك. وبعد دورة كاملة من \(L\) عمليات يكون كل عنصر قد رُبِّع مرة واحدة بالضبط، وتصبح القائمة المرتبة
$$2\lambda_1,2\lambda_2,\dots,2\lambda_L.$$
والنقطة الحاسمة أن المتراجحة التي أدخلتنا هذه المرحلة تبقى صحيحة بعد ضرب القائمة كلها في \(2\):
$$2(2\lambda_1)>2\lambda_L \iff 2\lambda_1>\lambda_L.$$
لذلك، ما إن ندخل هذه المنطقة حتى تستمر العملية على شكل دورات متماثلة من غير حاجة إلى تتبع كل خطوة على حدة.
لنفرض أن عدد العمليات المتبقية بعد المرحلة الصريحة هو \(r_{\mathrm{rem}}\). بما أن المرحلة المتوازنة تتقدم على شكل دورات كاملة فوق \(L\) عنصراً، نكتب
$$r_{\mathrm{rem}}=qL+s,\qquad 0\le s<L.$$
هذا يعني أن كل عنصر سيُربَّع \(q\) مرات إضافية، وأن أول \(s\) عناصر في الترتيب اللوغاريتمي الحالي ستحصل على تربيع إضافي واحد. أي إذا كان الترتيب الحالي هو
$$\lambda_1\le \lambda_2\le \cdots \le \lambda_L,$$
فإن العناصر ذات الترتيب \(1,2,\dots,s\) تحصل على \(q+1\) عمليات تربيع أخرى، بينما العناصر \(s+1,\dots,L\) تحصل على \(q\) فقط. وبهذه الطريقة يتحول ذيل طويل جداً من العملية إلى خارج قسمة وباقٍ فحسب.
إذا كان الباقي الحالي بترديد \(M=1234567891\) يساوي \(v\)، فإن تطبيق \(t\) عمليات تربيع إضافية يعطي
$$v^{2^t}\pmod{M}.$$
لذلك لا تحتاج المرحلة المجمعة إلا إلى الأسين \(2^q\) و\(2^{q+1}\). وبما أن \(M\) عدد أولي وأن القيم الابتدائية \(2,3,\dots,n\) كلها غير منعدمة بترديد \(M\)، فإن جميع البواقي اللاحقة تبقى غير منعدمة أيضاً. وعندئذ تسمح مبرهنة فيرما الصغرى باختزال الأسس بترديد \(M-1\):
$$a^k\equiv a^{\,k\bmod (M-1)}\pmod{M}\qquad (a\not\equiv 0\pmod{M}).$$
ولهذا تحسب التطبيقات \(2^q\bmod(M-1)\)، ثم تضاعفه للحصول على \(2^{q+1}\bmod(M-1)\)، وبعد ذلك تطبق الأسّية المعيارية السريعة على البواقي المخزنة من أجل جمع النتيجة النهائية.
القائمة الابتدائية هي \(2,3,4,5\). ويمكن تتبع أول ثلاث عمليات مباشرةً:
$$[2,3,4,5]\to [4,3,4,5]\to [4,9,4,5]\to [16,9,4,5].$$
إذن المجموع المطلوب يساوي
$$16+9+4+5=34,$$
وهو نفس مقدار التحقق الذي تستخدمه التطبيقات.
ولرؤية قاعدة التوزيع المجمّع وحدها، افترض أن اللوغاريتمات المرتبة بعد المرحلة الصريحة هي \(1.40,1.55,1.80,2.10\). بما أن \(2\cdot 1.40=2.80>2.10\)، فإن الاختيارات الأربع التالية تصبح إجبارية بهذا الترتيب نفسه. وإذا بقيت سبع عمليات، فإن
$$7=1\cdot 4+3,$$
أي إن كل عنصر سيُربَّع مرة إضافية، بينما تحصل العناصر الثلاثة الأولى على تربيع إضافي آخر.
تحتفظ تطبيقات C++ وPython وJava بمعلومتين لكل عنصر: مفتاح لوغاريتمي يُستخدم فقط للترتيب، والباقي الحالي بترديد \(1234567891\). ثم تهيئ بنية أولوية صغرى بالقيم \(2,3,\dots,n\)، وتتابع أيضاً أكبر لوغاريتم حالي.
ما دام مضاعفة أصغر لوغاريتم لا تجعله يتجاوز أكبر لوغاريتم حالي، تنفذ الشيفرة تحديثاً دقيقاً: تزيل العنصر الأصغر، تضاعف مفتاحه اللوغاريتمي، تربع باقيه بترديد العدد الأولي، تعيده إلى البنية، ثم تحدّث القيمة العظمى عند الحاجة.
وعندما تتحقق المتراجحة المتوازنة \(2\lambda_{\min}>\lambda_{\max}\)، تُسحب العناصر الباقية وتُرتب وفق القاعدة نفسها. بعد ذلك تحسب الشيفرة خارج القسمة \(q\) والباقي \(s\) عند قسمة عدد الخطوات المتبقية على \(L=n-1\)، وتحول ذلك إلى الأسين \(2^q\) و\(2^{q+1}\) بترديد \(M-1\)، ثم تطبق الأسّية المعيارية السريعة على كل باقٍ مخزن. تحصل أول \(s\) عناصر في الترتيب على الأس الأكبر، وتحصل بقية العناصر على الأس الأصغر، ثم تُجمع جميع المساهمات بترديد \(M\).
لنضع \(L=n-1\)، ولنرمز بـ \(u\) إلى عدد تحديثات بنية الأولوية الصريحة قبل الدخول في المرحلة المتوازنة. تبدأ التطبيقات بإدراج \(L\) عنصراً في بنية الأولوية، وهذه الكلفة تساوي \(O(L\log L)\). ثم تكلف المرحلة الصريحة \(O(u\log L)\)، لأن كل تحديث يتضمن إزالة عنصر وإعادة إدراجه.
بعد ذلك لا يبقى إلا ترتيب \(L\) عنصراً مرة واحدة، وحساب واحد لإيجاد \(2^q\bmod(M-1)\)، ثم \(L\) عمليات أسّية معيارية للبواقي النهائية. وعليه فإن زمن التنفيذ الكلي هو
$$O(u\log L+L\log L+L\log M+\log q),$$
وهو يختزل إلى \(O(u\log L+L\log L)\) إذا عومل الموديلوس على أنه ثابت. أما الذاكرة فهي \(O(L)\). الفائدة الأساسية أن الاعتماد على \(m\) الهائل يختفي بعد المرحلة الصريحة القصيرة.