This problem defines an integer sequence \(f(n)\) coming from the comfortable-distance construction and asks for the large prefix sum
$$S(n)=\sum_{k=1}^{n} f(k),$$
with the final result reported modulo \(10^8\). The implementations target values as large as \(n=10^{12}\), so a direct simulation of every term is completely impractical. The checkpoints built into the solution are
$$f(1)=1,\qquad f(15)=9,\qquad f(20)=6,\qquad f(500)=16,$$
and
$$S(20)=83,\qquad S(500)=13343.$$
The key observation is that the sequence is not generated term by term. Instead, it is organized into self-similar blocks on dyadic intervals, and each large block can be reduced to a smaller one plus three explicit arithmetic segments.
For each \(k \ge 0\), define the block
$$B_k=\bigl(f(2^k+1),f(2^k+2),\ldots,f(2^{k+1})\bigr),$$
so \(|B_k|=2^k\). Also define the power-of-two prefix and the internal block prefix by
$$P_k=\sum_{n=1}^{2^k} f(n),\qquad G_k(m)=\sum_{j=1}^{m} B_k(j),\qquad G_k(0)=0.$$
The first five blocks are stored explicitly:
$$B_0=(2),\qquad B_1=(2,4),$$
$$B_2=(3,6,2,6),\qquad B_3=(3,8,2,6,2,4,9,4),$$
$$B_4=(3,8,2,6,2,4,10,4,2,4,6,8,15,6,5,4).$$
Together with \(f(1)=1\), these values determine all small checkpoints. They also serve as the exact base of the recursion, so no approximation is introduced anywhere.
For \(k \ge 5\), set
$$r=2^{k-3}.$$
Then \(|B_k|=2^k=8r\), and the block decomposes into four consecutive pieces:
$$\text{Part I: } B_k(1),\ldots,B_k(3r)=B_{k-1}(1),\ldots,B_{k-1}(3r),$$
$$\text{Part II: } 4r+2,\ 2r,\ 2r-2,\ \ldots,\ 4,$$
$$\text{Part III: } 2,\ 4,\ 6,\ \ldots,\ 4r,$$
$$\text{Part IV: } 6r+3,\ 2r+2,\ 2r+1,\ \ldots,\ 4.$$
So the first \(3r\) values are copied from the first three quarters of the previous block, while the remaining \(5r\) values are generated by closed arithmetic rules. This is the structural reason the problem becomes logarithmic rather than linear.
Let the prefix sums of Parts II, III, and IV be denoted by \(A(r,m)\), \(E(m)\), and \(U(r,m)\).
For Part II, with \(1 \le m \le r\),
$$A(r,m)=4r+2+(m-1)(2r-m+2),$$
and the full segment sum is
$$\Sigma_A(r)=A(r,r)=r(r+5).$$
For Part III, with \(1 \le m \le 2r\),
$$E(m)=m(m+1),$$
because the segment is simply \(2,4,6,\ldots,2m\). Its full sum is
$$\Sigma_E(r)=E(2r)=4r^2+2r.$$
For Part IV, with \(1 \le m \le 2r\),
$$U(r,m)=6r+3+\frac{(m-1)(4r-m+6)}{2},$$
and the full segment sum is
$$\Sigma_U(r)=U(r,2r)=2r^2+11r.$$
If \(Q_k\) denotes the sum of the first three quarters of \(B_k\), then
$$Q_k=Q_{k-1}+\Sigma_A(r)+\Sigma_E(r)=Q_{k-1}+5r^2+7r,$$
and the whole block sum is
$$\Sigma_k=Q_k+\Sigma_U(r).$$
Write any \(n \ge 1\) in the form
$$n=2^k+t,\qquad 0 \le t \le 2^k.$$
Then
$$S(n)=P_k+G_k(t).$$
For \(k \le 4\), \(G_k(t)\) is read directly from the stored seed-block prefixes. For \(k \ge 5\), the block prefix is piecewise:
$$G_k(t)= \begin{cases} 0, & t=0,\\ G_{k-1}(t), & 1 \le t \le 3r,\\ Q_{k-1}+A(r,t-3r), & 3r \lt t \le 4r,\\ Q_{k-1}+\Sigma_A(r)+E(t-4r), & 4r \lt t \le 6r,\\ Q_{k-1}+\Sigma_A(r)+\Sigma_E(r)+U(r,t-6r), & 6r \lt t \le 8r. \end{cases}$$
Only the first case makes a recursive descent, and each descent lowers the block index by one. That is why the query depth is \(O(\log n)\).
The first nontrivial large block is \(B_5\), where \(r=2^{5-3}=4\). The first \(12\) entries are copied from the first \(12\) entries of \(B_4\):
$$3,8,2,6,2,4,10,4,2,4,6,8.$$
The three analytic pieces are then
$$18,8,6,4,$$
$$2,4,6,8,10,12,14,16,$$
and
$$27,10,9,8,7,6,5,4.$$
Hence
$$B_5=(3,8,2,6,2,4,10,4,2,4,6,8,18,8,6,4,2,4,6,8,10,12,14,16,27,10,9,8,7,6,5,4).$$
As a quick prefix check,
$$P_4=1+2+6+17+38=64,$$
and since \(20=16+4\),
$$S(20)=P_4+G_4(4)=64+(3+8+2+6)=83,$$
which matches the required checkpoint.
The C++, Python, and Java implementations all follow the same plan. They store the five seed blocks, build prefix tables for those exact values, and then precompute for each higher level three quantities: the sum of the whole block, the sum of the first three quarters of the block, and the prefix sum up to the next power of two.
When a query \(S(n)\) arrives, the implementation finds the highest power of two not exceeding \(n\). The stored prefix up to that power contributes immediately, and only the remainder inside one block still has to be evaluated. That remainder is handled by the piecewise formulas above, using recursion only when the remainder falls into the copied first segment.
The arithmetic is exact before the final reduction modulo \(10^8\). The C++ version uses 128-bit integers for intermediate totals, the Java version uses arbitrary-precision integers, and the Python version relies on Python's built-in unbounded integers.
If the target range is below \(2^{64}\), only \(64\) block levels are ever needed. Precomputing all stored block totals and power-of-two prefixes therefore costs \(O(\log n_{\max})\) time and \(O(\log n_{\max})\) memory. A single query for \(S(n)\) performs at most one descent per level, so its running time is \(O(\log n)\) and its extra working memory is \(O(1)\) beyond the precomputed tables.
Das Problem definiert eine ganzzahlige Folge \(f(n)\), die aus der Comfortable-Distance-Konstruktion entsteht, und verlangt die große Präfixsumme
$$S(n)=\sum_{k=1}^{n} f(k),$$
wobei das Endergebnis modulo \(10^8\) ausgegeben wird. Die Implementierungen zielen auf Werte bis \(n=10^{12}\), daher ist eine direkte Erzeugung aller Folgenglieder unmöglich. Als Kontrollwerte werden verwendet
$$f(1)=1,\qquad f(15)=9,\qquad f(20)=6,\qquad f(500)=16,$$
sowie
$$S(20)=83,\qquad S(500)=13343.$$
Der entscheidende Punkt ist, dass die Folge nicht Element für Element berechnet wird. Stattdessen wird sie in selbstähnliche Blöcke auf Intervallen der Form \((2^k,2^{k+1}]\) zerlegt, und jeder große Block reduziert sich auf einen kleineren Block plus drei explizite arithmetische Segmente.
Für jedes \(k \ge 0\) definieren wir den Block
$$B_k=\bigl(f(2^k+1),f(2^k+2),\ldots,f(2^{k+1})\bigr),$$
also \(|B_k|=2^k\). Außerdem bezeichnen wir die Zweierpotenz-Präfixsumme und die interne Block-Präfixsumme mit
$$P_k=\sum_{n=1}^{2^k} f(n),\qquad G_k(m)=\sum_{j=1}^{m} B_k(j),\qquad G_k(0)=0.$$
Die ersten fünf Blöcke sind explizit bekannt:
$$B_0=(2),\qquad B_1=(2,4),$$
$$B_2=(3,6,2,6),\qquad B_3=(3,8,2,6,2,4,9,4),$$
$$B_4=(3,8,2,6,2,4,10,4,2,4,6,8,15,6,5,4).$$
Zusammen mit \(f(1)=1\) bestimmen diese Werte alle kleinen Prüfstellen exakt. Gleichzeitig bilden sie die Basis der Rekursion, sodass nirgends eine Näherung eingeführt wird.
Für \(k \ge 5\) setzen wir
$$r=2^{k-3}.$$
Dann gilt \(|B_k|=2^k=8r\), und der Block zerfällt in vier aufeinanderfolgende Teile:
$$\text{Teil I: } B_k(1),\ldots,B_k(3r)=B_{k-1}(1),\ldots,B_{k-1}(3r),$$
$$\text{Teil II: } 4r+2,\ 2r,\ 2r-2,\ \ldots,\ 4,$$
$$\text{Teil III: } 2,\ 4,\ 6,\ \ldots,\ 4r,$$
$$\text{Teil IV: } 6r+3,\ 2r+2,\ 2r+1,\ \ldots,\ 4.$$
Die ersten \(3r\) Werte werden also aus den ersten drei Vierteln des vorherigen Blocks kopiert, während die restlichen \(5r\) Werte durch geschlossene arithmetische Regeln entstehen. Genau daraus folgt die logarithmische statt lineare Struktur.
Bezeichnen wir die Präfixsummen der Teile II, III und IV mit \(A(r,m)\), \(E(m)\) und \(U(r,m)\).
Für Teil II und \(1 \le m \le r\) gilt
$$A(r,m)=4r+2+(m-1)(2r-m+2),$$
mit gesamter Segmentsumme
$$\Sigma_A(r)=A(r,r)=r(r+5).$$
Für Teil III und \(1 \le m \le 2r\) gilt
$$E(m)=m(m+1),$$
denn dieses Segment ist einfach \(2,4,6,\ldots,2m\). Seine Gesamtsumme lautet
$$\Sigma_E(r)=E(2r)=4r^2+2r.$$
Für Teil IV und \(1 \le m \le 2r\) gilt
$$U(r,m)=6r+3+\frac{(m-1)(4r-m+6)}{2},$$
mit
$$\Sigma_U(r)=U(r,2r)=2r^2+11r.$$
Wenn \(Q_k\) die Summe der ersten drei Viertel von \(B_k\) bezeichnet, dann folgt
$$Q_k=Q_{k-1}+\Sigma_A(r)+\Sigma_E(r)=Q_{k-1}+5r^2+7r,$$
und die gesamte Blocksumme ist
$$\Sigma_k=Q_k+\Sigma_U(r).$$
Schreibe jedes \(n \ge 1\) in der Form
$$n=2^k+t,\qquad 0 \le t \le 2^k.$$
Dann gilt
$$S(n)=P_k+G_k(t).$$
Für \(k \le 4\) wird \(G_k(t)\) direkt aus den gespeicherten Präfixen der Startblöcke gelesen. Für \(k \ge 5\) erhält man stückweise
$$G_k(t)= \begin{cases} 0, & t=0,\\ G_{k-1}(t), & 1 \le t \le 3r,\\ Q_{k-1}+A(r,t-3r), & 3r \lt t \le 4r,\\ Q_{k-1}+\Sigma_A(r)+E(t-4r), & 4r \lt t \le 6r,\\ Q_{k-1}+\Sigma_A(r)+\Sigma_E(r)+U(r,t-6r), & 6r \lt t \le 8r. \end{cases}$$
Nur im ersten Fall steigt die Berechnung rekursiv eine Ebene tiefer ab, und jede solche Stufe verringert den Blockindex um eins. Deshalb ist die Tiefe \(O(\log n)\).
Der erste nichttriviale große Block ist \(B_5\) mit \(r=2^{5-3}=4\). Die ersten \(12\) Einträge werden aus den ersten \(12\) Einträgen von \(B_4\) übernommen:
$$3,8,2,6,2,4,10,4,2,4,6,8.$$
Die drei analytischen Teile lauten dann
$$18,8,6,4,$$
$$2,4,6,8,10,12,14,16,$$
und
$$27,10,9,8,7,6,5,4.$$
Damit ergibt sich
$$B_5=(3,8,2,6,2,4,10,4,2,4,6,8,18,8,6,4,2,4,6,8,10,12,14,16,27,10,9,8,7,6,5,4).$$
Als schnelle Präfixkontrolle gilt
$$P_4=1+2+6+17+38=64,$$
und wegen \(20=16+4\) folgt
$$S(20)=P_4+G_4(4)=64+(3+8+2+6)=83,$$
genau der geforderte Kontrollwert.
Die Implementierungen in C++, Python und Java folgen alle demselben Schema. Zuerst werden die fünf Startblöcke und ihre Präfixsummen gespeichert. Danach werden für jede höhere Ebene drei Werte vorab berechnet: die Summe des gesamten Blocks, die Summe seiner ersten drei Viertel und die Präfixsumme bis zur nächsten Zweierpotenz.
Bei einer Anfrage \(S(n)\) bestimmt die Implementierung die höchste Zweierpotenz, die \(n\) nicht überschreitet. Die bereits gespeicherte Summe bis zu dieser Grenze wird direkt addiert; nur der Rest innerhalb eines einzigen Blocks muss noch ausgewertet werden. Dieser Rest wird mit den obigen Stückformeln behandelt, wobei Rekursion nur dann nötig ist, wenn der Rest in den kopierten ersten Teil fällt.
Die Rechnung bleibt bis zur letzten Reduktion modulo \(10^8\) exakt. Die C++-Version verwendet 128-Bit-Ganzzahlen für Zwischensummen, die Java-Version beliebig große Ganzzahlen, und die Python-Version profitiert von den eingebauten unbeschränkten Ganzzahlen.
Solange der Zielbereich unter \(2^{64}\) liegt, werden höchstens \(64\) Blockebenen benötigt. Das Vorberechnen aller Block- und Zweierpotenzsummen kostet daher \(O(\log n_{\max})\) Zeit und \(O(\log n_{\max})\) Speicher. Eine einzelne Anfrage \(S(n)\) durchläuft höchstens eine Stufe pro Ebene und benötigt somit \(O(\log n)\) Zeit sowie \(O(1)\) zusätzlichen Arbeitsspeicher jenseits der vorberechneten Tabellen.
Bu problem, comfortable-distance yapısından gelen tam sayı dizisi \(f(n)\) için büyük ön-toplamı
$$S(n)=\sum_{k=1}^{n} f(k),$$
hesaplamayı ve sonucu \(10^8\) modunda vermeyi ister. Uygulamalar \(n=10^{12}\) gibi çok büyük değerlere yöneldiği için terimleri tek tek üretmek mümkün değildir. Çözümün kullandığı kontrol noktaları şunlardır:
$$f(1)=1,\qquad f(15)=9,\qquad f(20)=6,\qquad f(500)=16,$$
ve
$$S(20)=83,\qquad S(500)=13343.$$
Ana gözlem, dizinin eleman bazında değil, iki kuvvetleri arasındaki kendine benzer bloklar halinde düzenlenmesidir. Büyük her blok, daha küçük bir bloğun ön kısmı ile üç açık aritmetik parçaya ayrılabildiği için hesap logaritmik hale gelir.
Her \(k \ge 0\) için
$$B_k=\bigl(f(2^k+1),f(2^k+2),\ldots,f(2^{k+1})\bigr)$$
bloğunu tanımlayalım; böylece \(|B_k|=2^k\) olur. Ayrıca iki kuvvetine kadar olan toplamı ve blok içi ön-toplamı
$$P_k=\sum_{n=1}^{2^k} f(n),\qquad G_k(m)=\sum_{j=1}^{m} B_k(j),\qquad G_k(0)=0$$
ile gösterelim.
İlk beş blok açık biçimde şöyledir:
$$B_0=(2),\qquad B_1=(2,4),$$
$$B_2=(3,6,2,6),\qquad B_3=(3,8,2,6,2,4,9,4),$$
$$B_4=(3,8,2,6,2,4,10,4,2,4,6,8,15,6,5,4).$$
\(f(1)=1\) ile birlikte bu bloklar tüm küçük doğrulama değerlerini tam olarak belirler. Aynı zamanda özyinelemenin başlangıç verileri oldukları için hiçbir yaklaşım hatası oluşmaz.
\(k \ge 5\) için
$$r=2^{k-3}$$
olsun. O zaman \(|B_k|=2^k=8r\) ve blok dört ardışık parçadan oluşur:
$$\text{Parça I: } B_k(1),\ldots,B_k(3r)=B_{k-1}(1),\ldots,B_{k-1}(3r),$$
$$\text{Parça II: } 4r+2,\ 2r,\ 2r-2,\ \ldots,\ 4,$$
$$\text{Parça III: } 2,\ 4,\ 6,\ \ldots,\ 4r,$$
$$\text{Parça IV: } 6r+3,\ 2r+2,\ 2r+1,\ \ldots,\ 4.$$
Yani ilk \(3r\) değer, önceki bloğun ilk dörtte üçünün kopyasıdır; kalan \(5r\) değer ise kapalı aritmetik kurallarla üretilir. Hız kazandıran temel yapı tam olarak budur.
Parça II, III ve IV için ön-toplamları sırasıyla \(A(r,m)\), \(E(m)\) ve \(U(r,m)\) ile gösterelim.
Parça II için, \(1 \le m \le r\) aralığında,
$$A(r,m)=4r+2+(m-1)(2r-m+2),$$
ve tam segment toplamı
$$\Sigma_A(r)=A(r,r)=r(r+5)$$
olur.
Parça III için, \(1 \le m \le 2r\) aralığında,
$$E(m)=m(m+1),$$
çünkü bu bölüm basitçe \(2,4,6,\ldots,2m\) dizisidir. Tam toplam
$$\Sigma_E(r)=E(2r)=4r^2+2r$$
şeklindedir.
Parça IV için, \(1 \le m \le 2r\) aralığında,
$$U(r,m)=6r+3+\frac{(m-1)(4r-m+6)}{2},$$
ve buradan
$$\Sigma_U(r)=U(r,2r)=2r^2+11r$$
elde edilir.
\(Q_k\), \(B_k\) bloğunun ilk dörtte üçünün toplamı olsun. O zaman
$$Q_k=Q_{k-1}+\Sigma_A(r)+\Sigma_E(r)=Q_{k-1}+5r^2+7r,$$
ve tüm blok toplamı
$$\Sigma_k=Q_k+\Sigma_U(r)$$
olur.
Her \(n \ge 1\) sayısını
$$n=2^k+t,\qquad 0 \le t \le 2^k$$
şeklinde yazalım. Bu durumda
$$S(n)=P_k+G_k(t)$$
olur. \(k \le 4\) için \(G_k(t)\) doğrudan başlangıç bloklarının ön-toplam tablosundan okunur. \(k \ge 5\) olduğunda ise parça parça
$$G_k(t)= \begin{cases} 0, & t=0,\\ G_{k-1}(t), & 1 \le t \le 3r,\\ Q_{k-1}+A(r,t-3r), & 3r \lt t \le 4r,\\ Q_{k-1}+\Sigma_A(r)+E(t-4r), & 4r \lt t \le 6r,\\ Q_{k-1}+\Sigma_A(r)+\Sigma_E(r)+U(r,t-6r), & 6r \lt t \le 8r. \end{cases}$$
Rekürsiyon yalnızca ilk durumda kullanılır ve her adımda blok seviyesi bir azalır. Böylece sorgu derinliği \(O(\log n)\) olur.
İlk ciddi büyük blok \(B_5\)'tir ve burada \(r=2^{5-3}=4\) olur. İlk \(12\) eleman, \(B_4\)'ün ilk \(12\) elemanının aynısıdır:
$$3,8,2,6,2,4,10,4,2,4,6,8.$$
Sonraki üç analitik parça ise
$$18,8,6,4,$$
$$2,4,6,8,10,12,14,16,$$
ve
$$27,10,9,8,7,6,5,4$$
olur. Dolayısıyla
$$B_5=(3,8,2,6,2,4,10,4,2,4,6,8,18,8,6,4,2,4,6,8,10,12,14,16,27,10,9,8,7,6,5,4).$$
Hızlı bir ön-toplam kontrolü olarak
$$P_4=1+2+6+17+38=64$$
ve \(20=16+4\) olduğundan
$$S(20)=P_4+G_4(4)=64+(3+8+2+6)=83$$
elde edilir; bu da kontrol değeriyle aynıdır.
C++, Python ve Java uygulamalarının hepsi aynı planı izler. Önce beş başlangıç bloğu ve bunların ön-toplamları saklanır. Daha sonra üst seviyeler için üç nicelik önceden hesaplanır: tam blok toplamı, bloğun ilk dörtte üçünün toplamı ve iki kuvvet sınırlarına kadar olan toplamlar.
Bir \(S(n)\) sorgusunda uygulama, \(n\)'i aşmayan en büyük iki kuvvetini bulur. Bu sınıra kadar olan saklı toplam hemen eklenir; geriye tek bir blok içindeki kuyruk kısmı kalır. Bu kısım yukarıdaki parça formülleriyle çözülür ve sadece kopyalanan ilk bölüme düşerse rekürsif olarak bir seviye aşağı inilir.
Hesaplama, son aşamadaki \(10^8\) modu dışında tamamen tam sayılarla yapılır. C++ sürümü ara toplamlar için 128 bit, Java sürümü keyfi büyüklükte tam sayılar, Python sürümü ise yerleşik sınırsız tam sayılar kullanır.
Hedef aralık \(2^{64}\)'ün altında kaldığı sürece en fazla \(64\) blok seviyesi gerekir. Bu nedenle tüm blok toplamlarını ve iki kuvvetine kadar olan toplamları önceden hesaplamanın maliyeti \(O(\log n_{\max})\) zaman ve \(O(\log n_{\max})\) bellektir. Tek bir \(S(n)\) sorgusu seviye başına en fazla bir iniş yaptığı için çalışma süresi \(O(\log n)\), ek çalışma belleği ise önceden saklanan tablolar dışında \(O(1)\)'dir.
El problema define una sucesión entera \(f(n)\) asociada a la construcción de comfortable distance y pide la suma prefija grande
$$S(n)=\sum_{k=1}^{n} f(k),$$
con resultado final módulo \(10^8\). Las implementaciones apuntan a valores tan grandes como \(n=10^{12}\), así que generar todos los términos uno por uno es inviable. Los puntos de control incorporados son
$$f(1)=1,\qquad f(15)=9,\qquad f(20)=6,\qquad f(500)=16,$$
y también
$$S(20)=83,\qquad S(500)=13343.$$
La observación central es que la sucesión no se construye término a término. En cambio, se agrupa en bloques autosimilares sobre intervalos diádicos, y cada bloque grande se descompone en un prefijo copiado de un bloque anterior más tres segmentos aritméticos explícitos.
Para cada \(k \ge 0\), definimos el bloque
$$B_k=\bigl(f(2^k+1),f(2^k+2),\ldots,f(2^{k+1})\bigr),$$
de modo que \(|B_k|=2^k\). Además, definimos la suma prefija hasta una potencia de dos y la suma prefija interna del bloque por
$$P_k=\sum_{n=1}^{2^k} f(n),\qquad G_k(m)=\sum_{j=1}^{m} B_k(j),\qquad G_k(0)=0.$$
Los primeros cinco bloques se conocen exactamente:
$$B_0=(2),\qquad B_1=(2,4),$$
$$B_2=(3,6,2,6),\qquad B_3=(3,8,2,6,2,4,9,4),$$
$$B_4=(3,8,2,6,2,4,10,4,2,4,6,8,15,6,5,4).$$
Junto con \(f(1)=1\), estos bloques fijan todos los controles pequeños y forman la base exacta de la recurrencia.
Para \(k \ge 5\), ponemos
$$r=2^{k-3}.$$
Entonces \(|B_k|=2^k=8r\), y el bloque se divide en cuatro partes consecutivas:
$$\text{Parte I: } B_k(1),\ldots,B_k(3r)=B_{k-1}(1),\ldots,B_{k-1}(3r),$$
$$\text{Parte II: } 4r+2,\ 2r,\ 2r-2,\ \ldots,\ 4,$$
$$\text{Parte III: } 2,\ 4,\ 6,\ \ldots,\ 4r,$$
$$\text{Parte IV: } 6r+3,\ 2r+2,\ 2r+1,\ \ldots,\ 4.$$
Así, los primeros \(3r\) valores copian los tres primeros cuartos del bloque anterior, y los \(5r\) restantes se generan con reglas aritméticas cerradas. Esa autosimilitud es lo que vuelve eficiente el cálculo.
Denotemos por \(A(r,m)\), \(E(m)\) y \(U(r,m)\) las sumas prefijas de las Partes II, III y IV.
Para la Parte II, con \(1 \le m \le r\),
$$A(r,m)=4r+2+(m-1)(2r-m+2),$$
y la suma completa del segmento es
$$\Sigma_A(r)=A(r,r)=r(r+5).$$
Para la Parte III, con \(1 \le m \le 2r\),
$$E(m)=m(m+1),$$
porque el segmento es simplemente \(2,4,6,\ldots,2m\). Su suma completa vale
$$\Sigma_E(r)=E(2r)=4r^2+2r.$$
Para la Parte IV, con \(1 \le m \le 2r\),
$$U(r,m)=6r+3+\frac{(m-1)(4r-m+6)}{2},$$
y por tanto
$$\Sigma_U(r)=U(r,2r)=2r^2+11r.$$
Si \(Q_k\) es la suma de los primeros tres cuartos de \(B_k\), entonces
$$Q_k=Q_{k-1}+\Sigma_A(r)+\Sigma_E(r)=Q_{k-1}+5r^2+7r,$$
y la suma total del bloque es
$$\Sigma_k=Q_k+\Sigma_U(r).$$
Escribimos cualquier \(n \ge 1\) como
$$n=2^k+t,\qquad 0 \le t \le 2^k.$$
Entonces
$$S(n)=P_k+G_k(t).$$
Si \(k \le 4\), \(G_k(t)\) se obtiene directamente de las tablas base. Si \(k \ge 5\), se usa la fórmula por tramos
$$G_k(t)= \begin{cases} 0, & t=0,\\ G_{k-1}(t), & 1 \le t \le 3r,\\ Q_{k-1}+A(r,t-3r), & 3r \lt t \le 4r,\\ Q_{k-1}+\Sigma_A(r)+E(t-4r), & 4r \lt t \le 6r,\\ Q_{k-1}+\Sigma_A(r)+\Sigma_E(r)+U(r,t-6r), & 6r \lt t \le 8r. \end{cases}$$
Solo el primer caso desciende recursivamente, y cada descenso reduce el nivel del bloque en una unidad. Por eso la profundidad total es \(O(\log n)\).
El primer bloque grande no trivial es \(B_5\), donde \(r=2^{5-3}=4\). Los primeros \(12\) términos se copian de los primeros \(12\) términos de \(B_4\):
$$3,8,2,6,2,4,10,4,2,4,6,8.$$
Las tres partes analíticas son
$$18,8,6,4,$$
$$2,4,6,8,10,12,14,16,$$
y
$$27,10,9,8,7,6,5,4.$$
Por lo tanto,
$$B_5=(3,8,2,6,2,4,10,4,2,4,6,8,18,8,6,4,2,4,6,8,10,12,14,16,27,10,9,8,7,6,5,4).$$
Como comprobación rápida,
$$P_4=1+2+6+17+38=64,$$
y como \(20=16+4\),
$$S(20)=P_4+G_4(4)=64+(3+8+2+6)=83,$$
que coincide con el punto de control requerido.
Las implementaciones en C++, Python y Java siguen exactamente la misma estrategia. Guardan los cinco bloques base, construyen sus tablas de sumas prefijas y luego precalculan, para cada nivel superior, tres cantidades: la suma completa del bloque, la suma de sus primeros tres cuartos y la suma prefija hasta la siguiente potencia de dos.
Cuando llega una consulta \(S(n)\), la implementación encuentra la mayor potencia de dos no superior a \(n\). La contribución hasta esa frontera ya está almacenada, y solo queda evaluar el resto dentro de un bloque. Ese resto se resuelve con las fórmulas por tramos anteriores, usando recursión solo cuando cae dentro del primer segmento copiado.
La aritmética es exacta antes de la reducción final módulo \(10^8\). La versión en C++ usa enteros de 128 bits para las sumas intermedias, la de Java usa enteros de precisión arbitraria y la de Python aprovecha sus enteros sin límite fijo.
Mientras el rango objetivo esté por debajo de \(2^{64}\), solo hacen falta \(64\) niveles de bloque. Por ello, el precálculo de todas las sumas de bloque y de las sumas hasta potencias de dos cuesta \(O(\log n_{\max})\) tiempo y \(O(\log n_{\max})\) memoria. Una consulta individual \(S(n)\) realiza como máximo un descenso por nivel, de modo que tarda \(O(\log n)\) y usa \(O(1)\) memoria adicional aparte de las tablas precalculadas.
本题定义了一个来自 comfortable distance 构造的整数序列 \(f(n)\)，要求计算巨大的前缀和
$$S(n)=\sum_{k=1}^{n} f(k),$$
并把最终结果对 \(10^8\) 取模。实现面向的规模可达到 \(n=10^{12}\)，因此逐项生成整个序列根本不可行。程序中用来校验正确性的检查点是
$$f(1)=1,\qquad f(15)=9,\qquad f(20)=6,\qquad f(500)=16,$$
以及
$$S(20)=83,\qquad S(500)=13343.$$
真正的突破点在于：这个序列不是按索引顺序逐个求值，而是按二进制区间组织成自相似的块。每个较大的块都可以写成“前一层块的前三个四分之一前缀”加上三个完全显式的等差型片段，因此查询前缀和时只需要沿着块层级递归下降，而不需要扫描所有项。
对每个 \(k \ge 0\)，定义块
$$B_k=\bigl(f(2^k+1),f(2^k+2),\ldots,f(2^{k+1})\bigr),$$
因此 \(|B_k|=2^k\)。再定义到二次幂边界为止的前缀和，以及块内部的前缀和：
$$P_k=\sum_{n=1}^{2^k} f(n),\qquad G_k(m)=\sum_{j=1}^{m} B_k(j),\qquad G_k(0)=0.$$
前五个块是直接给定的：
$$B_0=(2),\qquad B_1=(2,4),$$
$$B_2=(3,6,2,6),\qquad B_3=(3,8,2,6,2,4,9,4),$$
$$B_4=(3,8,2,6,2,4,10,4,2,4,6,8,15,6,5,4).$$
再配合 \(f(1)=1\)，就能完全确定所有小规模检查点。这些初始块同时也是整个递归体系的精确种子，因此后面的公式不是近似，而是严格重构。
当 \(k \ge 5\) 时，令
$$r=2^{k-3}.$$
于是 \(|B_k|=2^k=8r\)。程序中的递推表明，整个块恰好由四段首尾相接的结构组成：
$$\text{第一段： } B_k(1),\ldots,B_k(3r)=B_{k-1}(1),\ldots,B_{k-1}(3r),$$
$$\text{第二段： } 4r+2,\ 2r,\ 2r-2,\ \ldots,\ 4,$$
$$\text{第三段： } 2,\ 4,\ 6,\ \ldots,\ 4r,$$
$$\text{第四段： } 6r+3,\ 2r+2,\ 2r+1,\ \ldots,\ 4.$$
也就是说，前 \(3r\) 项直接复制上一层块的前三个四分之一前缀；后面 \(5r\) 项则由三段显式的数列组成。因为复制段只引用上一层的前缀，所以递归永远只会沿块层级下降，而不会回到逐项计算。
把第二、第三、第四段的前缀和分别记为 \(A(r,m)\)、\(E(m)\)、\(U(r,m)\)。
第二段在 \(1 \le m \le r\) 时满足
$$A(r,m)=4r+2+(m-1)(2r-m+2),$$
它的整段总和为
$$\Sigma_A(r)=A(r,r)=r(r+5).$$
第三段是最简单的偶数递增列，所以在 \(1 \le m \le 2r\) 时
$$E(m)=m(m+1),$$
从而整段总和是
$$\Sigma_E(r)=E(2r)=4r^2+2r.$$
第四段的前缀和在 \(1 \le m \le 2r\) 时为
$$U(r,m)=6r+3+\frac{(m-1)(4r-m+6)}{2},$$
对应整段总和
$$\Sigma_U(r)=U(r,2r)=2r^2+11r.$$
如果记 \(Q_k\) 为块 \(B_k\) 前四分之三部分的总和，那么
$$Q_k=Q_{k-1}+\Sigma_A(r)+\Sigma_E(r)=Q_{k-1}+5r^2+7r,$$
而整块总和则是
$$\Sigma_k=Q_k+\Sigma_U(r).$$
这两个量正是高层预处理时最重要的缓存内容：一个负责处理“块内前三个四分之三”的情况，另一个负责把整块加入到二次幂前缀和里。
对任意 \(n \ge 1\)，写成
$$n=2^k+t,\qquad 0 \le t \le 2^k.$$
那么有
$$S(n)=P_k+G_k(t).$$
当 \(k \le 4\) 时，\(G_k(t)\) 直接从初始块的前缀表读取。当 \(k \ge 5\) 时，块前缀满足分段公式
$$G_k(t)= \begin{cases} 0, & t=0,\\ G_{k-1}(t), & 1 \le t \le 3r,\\ Q_{k-1}+A(r,t-3r), & 3r \lt t \le 4r,\\ Q_{k-1}+\Sigma_A(r)+E(t-4r), & 4r \lt t \le 6r,\\ Q_{k-1}+\Sigma_A(r)+\Sigma_E(r)+U(r,t-6r), & 6r \lt t \le 8r. \end{cases}$$
只有第一种情况会继续递归到更小的块，而且每次都会把块编号减少 \(1\)。因此一次查询的层数只和 \(n\) 的二进制位数成正比，也就是 \(O(\log n)\)。
第一个真正需要递推生成的大块是 \(B_5\)，这时 \(r=2^{5-3}=4\)。它的前 \(12\) 项直接复制 \(B_4\) 的前 \(12\) 项：
$$3,8,2,6,2,4,10,4,2,4,6,8.$$
接着三段显式数列分别是
$$18,8,6,4,$$
$$2,4,6,8,10,12,14,16,$$
以及
$$27,10,9,8,7,6,5,4.$$
所以
$$B_5=(3,8,2,6,2,4,10,4,2,4,6,8,18,8,6,4,2,4,6,8,10,12,14,16,27,10,9,8,7,6,5,4).$$
再看一个前缀和检查：因为
$$P_4=1+2+6+17+38=64,$$
而 \(20=16+4\)，所以
$$S(20)=P_4+G_4(4)=64+(3+8+2+6)=83,$$
恰好与检查点一致。这说明“二次幂边界前缀 + 一个块内前缀”的分解方式是完全正确的。
C++、Python 和 Java 的实现采用同一套思路。它们先保存五个初始块以及这些块的前缀和，然后对更高层的每一级预处理三个量：整块和、块前四分之三的和，以及到各个二次幂边界为止的累计前缀和。
收到一个 \(S(n)\) 查询时，实现先找出不超过 \(n\) 的最大二次幂。到这个边界为止的贡献可以直接从预处理结果中取出，剩余部分只落在一个块的内部。随后用上面的分段公式计算这部分；只有当剩余位置落入复制段时，才递归到更小一级的块。
所有中间计算在最终模 \(10^8\) 之前都保持精确。C++ 版本使用 128 位整数保存中间总和，Java 版本使用任意精度整数，Python 版本则依赖语言内建的大整数能力。
如果目标范围不超过 \(2^{64}\)，那么只需要 \(64\) 个块层级。于是，预处理所有块总和和二次幂边界前缀和的代价是 \(O(\log n_{\max})\) 时间和 \(O(\log n_{\max})\) 空间。单次 \(S(n)\) 查询在每一层最多只下降一次，因此总时间复杂度为 \(O(\log n)\)，除预处理表之外的额外工作空间为 \(O(1)\)。
В задаче задана целочисленная последовательность \(f(n)\), возникающая из конструкции comfortable distance, и требуется вычислить большую префиксную сумму
$$S(n)=\sum_{k=1}^{n} f(k),$$
а затем взять результат по модулю \(10^8\). Реализации ориентированы на значения вплоть до \(n=10^{12}\), поэтому линейная генерация всех членов невозможна. Встроенные контрольные значения таковы:
$$f(1)=1,\qquad f(15)=9,\qquad f(20)=6,\qquad f(500)=16,$$
и
$$S(20)=83,\qquad S(500)=13343.$$
Ключевая идея состоит в том, что последовательность организована не по отдельным индексам, а по самоподобным блокам на двоичных интервалах. Каждый большой блок раскладывается на копируемый префикс предыдущего уровня и три явных арифметических сегмента.
Для каждого \(k \ge 0\) определим блок
$$B_k=\bigl(f(2^k+1),f(2^k+2),\ldots,f(2^{k+1})\bigr),$$
так что \(|B_k|=2^k\). Кроме того, введем сумму до степени двойки и префикс внутри блока:
$$P_k=\sum_{n=1}^{2^k} f(n),\qquad G_k(m)=\sum_{j=1}^{m} B_k(j),\qquad G_k(0)=0.$$
Первые пять блоков заданы явно:
$$B_0=(2),\qquad B_1=(2,4),$$
$$B_2=(3,6,2,6),\qquad B_3=(3,8,2,6,2,4,9,4),$$
$$B_4=(3,8,2,6,2,4,10,4,2,4,6,8,15,6,5,4).$$
Совместно с \(f(1)=1\) эти блоки полностью определяют все малые контрольные точки и служат точной базой рекурсии.
Для \(k \ge 5\) положим
$$r=2^{k-3}.$$
Тогда \(|B_k|=2^k=8r\), и блок имеет следующий вид:
$$\text{Часть I: } B_k(1),\ldots,B_k(3r)=B_{k-1}(1),\ldots,B_{k-1}(3r),$$
$$\text{Часть II: } 4r+2,\ 2r,\ 2r-2,\ \ldots,\ 4,$$
$$\text{Часть III: } 2,\ 4,\ 6,\ \ldots,\ 4r,$$
$$\text{Часть IV: } 6r+3,\ 2r+2,\ 2r+1,\ \ldots,\ 4.$$
То есть первые \(3r\) элементов просто копируют первые три четверти предыдущего блока, а оставшиеся \(5r\) элементов задаются замкнутыми арифметическими правилами. Благодаря этому вычисление становится логарифмическим.
Обозначим префиксные суммы частей II, III и IV через \(A(r,m)\), \(E(m)\) и \(U(r,m)\).
Для части II, при \(1 \le m \le r\), имеем
$$A(r,m)=4r+2+(m-1)(2r-m+2),$$
а полная сумма сегмента равна
$$\Sigma_A(r)=A(r,r)=r(r+5).$$
Для части III, при \(1 \le m \le 2r\),
$$E(m)=m(m+1),$$
поскольку это просто последовательность \(2,4,6,\ldots,2m\). Отсюда
$$\Sigma_E(r)=E(2r)=4r^2+2r.$$
Для части IV, при \(1 \le m \le 2r\),
$$U(r,m)=6r+3+\frac{(m-1)(4r-m+6)}{2},$$
и потому
$$\Sigma_U(r)=U(r,2r)=2r^2+11r.$$
Если \(Q_k\) обозначает сумму первых трех четвертей блока \(B_k\), то
$$Q_k=Q_{k-1}+\Sigma_A(r)+\Sigma_E(r)=Q_{k-1}+5r^2+7r,$$
а полная сумма блока равна
$$\Sigma_k=Q_k+\Sigma_U(r).$$
Представим любое \(n \ge 1\) в виде
$$n=2^k+t,\qquad 0 \le t \le 2^k.$$
Тогда
$$S(n)=P_k+G_k(t).$$
Для \(k \le 4\) значение \(G_k(t)\) берется прямо из таблицы базовых префиксов. Для \(k \ge 5\) используется кусочная формула
$$G_k(t)= \begin{cases} 0, & t=0,\\ G_{k-1}(t), & 1 \le t \le 3r,\\ Q_{k-1}+A(r,t-3r), & 3r \lt t \le 4r,\\ Q_{k-1}+\Sigma_A(r)+E(t-4r), & 4r \lt t \le 6r,\\ Q_{k-1}+\Sigma_A(r)+\Sigma_E(r)+U(r,t-6r), & 6r \lt t \le 8r. \end{cases}$$
Рекурсивный спуск происходит только в первом случае, и каждый раз уровень блока уменьшается на единицу. Поэтому глубина вычисления равна \(O(\log n)\).
Первый нетривиальный большой блок — это \(B_5\), где \(r=2^{5-3}=4\). Его первые \(12\) элементов копируются из первых \(12\) элементов блока \(B_4\):
$$3,8,2,6,2,4,10,4,2,4,6,8.$$
Три аналитические части затем равны
$$18,8,6,4,$$
$$2,4,6,8,10,12,14,16,$$
и
$$27,10,9,8,7,6,5,4.$$
Следовательно,
$$B_5=(3,8,2,6,2,4,10,4,2,4,6,8,18,8,6,4,2,4,6,8,10,12,14,16,27,10,9,8,7,6,5,4).$$
Быстрая проверка префикса:
$$P_4=1+2+6+17+38=64,$$
а поскольку \(20=16+4\), получаем
$$S(20)=P_4+G_4(4)=64+(3+8+2+6)=83,$$
что точно совпадает с контрольным значением.
Реализации на C++, Python и Java используют одну и ту же схему. Сначала сохраняются пять базовых блоков и их префиксные суммы. Затем для каждого более высокого уровня заранее вычисляются три величины: сумма всего блока, сумма его первых трех четвертей и сумма до соответствующей степени двойки.
При запросе \(S(n)\) реализация находит наибольшую степень двойки, не превосходящую \(n\). Вклад до этой границы уже известен из таблицы, а дальше остается вычислить только хвост внутри одного блока. Для этого применяется приведенная выше кусочная формула; рекурсия нужна лишь тогда, когда хвост попадает в копируемый первый сегмент.
Все промежуточные вычисления выполняются точно до самой последней операции взятия по модулю \(10^8\). В версии на C++ используются 128-битные целые, в версии на Java — целые произвольной точности, а в версии на Python — встроенные длинные целые.
Если максимальное рассматриваемое значение меньше \(2^{64}\), то достаточно всего \(64\) уровней блоков. Поэтому предварительное вычисление всех блоковых сумм и сумм на границах степеней двойки требует \(O(\log n_{\max})\) времени и \(O(\log n_{\max})\) памяти. Один запрос \(S(n)\) делает не более одного спуска на каждом уровне, значит его время работы равно \(O(\log n)\), а дополнительная память сверх подготовленных таблиц равна \(O(1)\).
تعرّف المسألة متتالية صحيحة \(f(n)\) ناتجة عن بناء comfortable distance، والمطلوب هو حساب المجموع التراكمي الكبير
$$S(n)=\sum_{k=1}^{n} f(k),$$
ثم إعطاء النتيجة بترديد \(10^8\). التطبيقات تستهدف قيماً تصل إلى \(n=10^{12}\)، ولذلك فإن توليد الحدود واحداً واحداً غير عملي تماماً. نقاط التحقق المستخدمة هي
$$f(1)=1,\qquad f(15)=9,\qquad f(20)=6,\qquad f(500)=16,$$
وكذلك
$$S(20)=83,\qquad S(500)=13343.$$
الفكرة الحاسمة هي أن المتتالية لا تُحسب حدّاً بعد حد، بل تُنظَّم في كتل ذات تشابه ذاتي على مجالات قوى العدد \(2\). وكل كتلة كبيرة يمكن كتابتها على صورة مقدمة منسوخة من كتلة أصغر بالإضافة إلى ثلاثة مقاطع حسابية صريحة.
لكل \(k \ge 0\) نعرّف الكتلة
$$B_k=\bigl(f(2^k+1),f(2^k+2),\ldots,f(2^{k+1})\bigr),$$
وبالتالي فإن \(|B_k|=2^k\). كما نعرّف مجموع القيم حتى قوة للعدد \(2\)، ومجموع المقدمة داخل الكتلة، بالصيغة
$$P_k=\sum_{n=1}^{2^k} f(n),\qquad G_k(m)=\sum_{j=1}^{m} B_k(j),\qquad G_k(0)=0.$$
أول خمس كتل معلومة صراحة:
$$B_0=(2),\qquad B_1=(2,4),$$
$$B_2=(3,6,2,6),\qquad B_3=(3,8,2,6,2,4,9,4),$$
$$B_4=(3,8,2,6,2,4,10,4,2,4,6,8,15,6,5,4).$$
ومع القيمة \(f(1)=1\) تكفي هذه الكتل لتحديد جميع نقاط التحقق الصغيرة بدقة تامة. كما أنها تشكّل قاعدة الاستدعاء التكراري، لذا لا توجد أي تقريبية في الحل.
عندما يكون \(k \ge 5\)، نضع
$$r=2^{k-3}.$$
عندئذٍ يكون طول الكتلة \(|B_k|=2^k=8r\)، وتتفكك الكتلة إلى أربعة أجزاء متتابعة:
الجزء الأول:
$$B_k(1),\ldots,B_k(3r)=B_{k-1}(1),\ldots,B_{k-1}(3r).$$
الجزء الثاني:
$$4r+2,\ 2r,\ 2r-2,\ \ldots,\ 4.$$
الجزء الثالث:
$$2,\ 4,\ 6,\ \ldots,\ 4r.$$
الجزء الرابع:
$$6r+3,\ 2r+2,\ 2r+1,\ \ldots,\ 4.$$
إذن أول \(3r\) حدود هي نسخة من أول ثلاثة أرباع الكتلة السابقة، أما بقية \(5r\) حدود فتنتج من قواعد حسابية مغلقة. وهذا هو السبب الحقيقي وراء إمكانية الإجابة في زمن لوغاريتمي.
لنرمز إلى مجاميع المقدمات للأجزاء الثاني والثالث والرابع بالرموز \(A(r,m)\) و\(E(m)\) و\(U(r,m)\).
في الجزء الثاني، عندما \(1 \le m \le r\)، لدينا
$$A(r,m)=4r+2+(m-1)(2r-m+2),$$
ومجموع هذا الجزء كاملاً هو
$$\Sigma_A(r)=A(r,r)=r(r+5).$$
وفي الجزء الثالث، عندما \(1 \le m \le 2r\)، نجد
$$E(m)=m(m+1),$$
لأن هذا الجزء هو ببساطة السلسلة \(2,4,6,\ldots,2m\). ومن ثم يكون مجموعه الكامل
$$\Sigma_E(r)=E(2r)=4r^2+2r.$$
أما الجزء الرابع، فعندما \(1 \le m \le 2r\)، فإن
$$U(r,m)=6r+3+\frac{(m-1)(4r-m+6)}{2},$$
ومنها نحصل على
$$\Sigma_U(r)=U(r,2r)=2r^2+11r.$$
إذا كان \(Q_k\) هو مجموع أول ثلاثة أرباع الكتلة \(B_k\)، فلدينا
$$Q_k=Q_{k-1}+\Sigma_A(r)+\Sigma_E(r)=Q_{k-1}+5r^2+7r,$$
بينما مجموع الكتلة كلها يساوي
$$\Sigma_k=Q_k+\Sigma_U(r).$$
نكتب أي \(n \ge 1\) على الصورة
$$n=2^k+t,\qquad 0 \le t \le 2^k.$$
وعندئذٍ
$$S(n)=P_k+G_k(t).$$
إذا كان \(k \le 4\)، فإن \(G_k(t)\) يُقرأ مباشرة من جداول الكتل الابتدائية. أما عندما \(k \ge 5\)، فنستخدم الصيغة القطعية
$$G_k(t)= \begin{cases} 0, & t=0,\\ G_{k-1}(t), & 1 \le t \le 3r,\\ Q_{k-1}+A(r,t-3r), & 3r \lt t \le 4r,\\ Q_{k-1}+\Sigma_A(r)+E(t-4r), & 4r \lt t \le 6r,\\ Q_{k-1}+\Sigma_A(r)+\Sigma_E(r)+U(r,t-6r), & 6r \lt t \le 8r. \end{cases}$$
الحالة الأولى فقط هي التي تستدعي نزولاً تكرارياً إلى مستوى أصغر، وكل نزول يقلل فهرس الكتلة بمقدار واحد. لذلك يكون عمق الاستعلام \(O(\log n)\).
أول كتلة كبيرة غير بدائية هي \(B_5\)، وفيها \(r=2^{5-3}=4\). أول \(12\) عنصراً منها يساوي أول \(12\) عنصراً من \(B_4\):
$$3,8,2,6,2,4,10,4,2,4,6,8.$$
ثم تصبح المقاطع التحليلية الثلاثة
$$18,8,6,4,$$
$$2,4,6,8,10,12,14,16,$$
و
$$27,10,9,8,7,6,5,4.$$
ومن ثم
$$B_5=(3,8,2,6,2,4,10,4,2,4,6,8,18,8,6,4,2,4,6,8,10,12,14,16,27,10,9,8,7,6,5,4).$$
وللتحقق السريع من مجموع بادئ، لدينا
$$P_4=1+2+6+17+38=64,$$
وبما أن \(20=16+4\)، فإن
$$S(20)=P_4+G_4(4)=64+(3+8+2+6)=83,$$
وهو تماماً مقدار التحقق المطلوب.
تتبع تطبيقات C++ وPython وJava الخطة نفسها. فهي تخزن أولاً الكتل الابتدائية الخمس وجداول مجاميعها البادئة، ثم تُجري معالجة مسبقة لكل مستوى أعلى فتحتفظ بثلاث كميات: مجموع الكتلة كاملة، ومجموع أول ثلاثة أرباع منها، والمجموع البادئ حتى حدود قوى العدد \(2\).
عند وصول طلب \(S(n)\)، تبحث الشيفرة عن أكبر قوة للعدد \(2\) لا تتجاوز \(n\). المساهمة حتى هذه الحدود تكون معروفة مسبقاً، ولا يبقى إلا ذيل يقع داخل كتلة واحدة. هذا الذيل يُقيَّم بواسطة الصيغ القطعية السابقة، ولا يُستخدم الاستدعاء التكراري إلا إذا وقع الذيل داخل الجزء الأول المنسوخ.
كل الحسابات تتم بدقة كاملة قبل الاختزال النهائي بترديد \(10^8\). تستخدم نسخة C++ أعداداً صحيحة بعرض 128 بت في المجاميع الوسيطة، وتستخدم نسخة Java أعداداً صحيحة ذات دقة غير محدودة، بينما تعتمد نسخة Python على الأعداد الصحيحة الكبيرة المدمجة في اللغة.
إذا كان المجال المطلوب أقل من \(2^{64}\)، فلن نحتاج إلى أكثر من \(64\) مستوى من الكتل. لذلك فإن المعالجة المسبقة لجميع مجاميع الكتل ولمجاميع حدود قوى العدد \(2\) تكلف \(O(\log n_{\max})\) زمناً و\(O(\log n_{\max})\) ذاكرة. أما الاستعلام الواحد عن \(S(n)\) فينزل على الأكثر مرة واحدة في كل مستوى، ولذلك فإن زمنه \(O(\log n)\)، وذاكرته الإضافية \(O(1)\) فوق الجداول المحسوبة مسبقاً.