The sequence is defined by
$$S(k)=p_k^k \bmod 10007,\qquad S_2(k)=S(k)+S\left(\left\lfloor\frac{k}{10000}\right\rfloor+1\right),$$
where \(p_k\) is the \(k\)-th prime. For each contiguous block \(S_2(i),S_2(i+1),\dots,S_2(i+K-1)\), let \(M(i,i+K-1)\) be its median, using the average of the two middle values when \(K\) is even. The target quantity is
$$F(n,K)=\sum_{i=1}^{n-K+1} M(i,i+K-1).$$
A direct recomputation of every window median would be far too slow. The implementations succeed because the sequence can be generated online, every value lies in a very small fixed range, and a frequency structure can therefore answer median queries without re-sorting each window.
The solution combines two observations: generating each term of \(S_2\) is cheap once the primes are streamed in order, and medians of a multiset can be recovered from prefix frequencies.
Since \(10007\) is prime, every prime \(p_k\neq 10007\) is invertible modulo \(10007\). Therefore Fermat's little theorem allows the exponent to be reduced modulo
$$\varphi(10007)=10006.$$
So, except for the single case \(p_k=10007\), we may compute
$$p_k^k \bmod 10007 = p_k^{\,k \bmod 10006} \bmod 10007.$$
This turns each term into one fast modular exponentiation once the \(k\)-th prime is known. The C++, Python, and Java implementations all estimate a safe upper bound for the \(n\)-th prime and use an odd-only sieve to enumerate primes in increasing order.
By construction,
$$0\le S(k)\le 10006.$$
Hence
$$0\le S_2(k)=S(k)+S\left(\left\lfloor\frac{k}{10000}\right\rfloor+1\right)\le 20012.$$
This bound is the key simplification. Every window value lies in the fixed domain
$$\{0,1,2,\dots,20012\},$$
whose size is only \(V=20013\). For the target instance \(n=10^7\), the shifted index \(\left\lfloor k/10000\right\rfloor+1\) never exceeds \(1001\), so the implementation only needs to remember those early sequence values to form the second summand.
For one window of length \(K\), let \(f_v\) be the number of occurrences of value \(v\), and define the prefix counts
$$P(v)=\sum_{x=0}^{v} f_x.$$
The \(t\)-th smallest value in the window is the unique \(v\) satisfying
$$P(v-1) \lt t \le P(v).$$
If the sorted window values are \(a_1\le a_2\le \cdots \le a_K\), then setting
$$t_1=\left\lfloor\frac{K+1}{2}\right\rfloor,\qquad t_2=\left\lfloor\frac{K+2}{2}\right\rfloor$$
gives the compact formula
$$M=\frac{a_{t_1}+a_{t_2}}{2}.$$
So every window median reduces to finding one or two order statistics inside a frequency table.
Moving the window by one position changes only two elements: one outgoing value disappears and one incoming value appears. In frequency form this is
$$f_{v_{\text{out}}}\leftarrow f_{v_{\text{out}}}-1,\qquad f_{v_{\text{in}}}\leftarrow f_{v_{\text{in}}}+1.$$
A Fenwick tree stores the array \((f_0,f_1,\dots,f_{20012})\), supports both updates in \(O(\log V)\), and can also search for the smallest value whose prefix sum reaches a target rank \(t\). That makes median extraction \(O(\log V)\) per window as well.
When \(K\) is even, a median may end in \(0.5\). Instead of using floating-point arithmetic, the implementation accumulates the doubled contribution
$$2M=a_{t_1}+a_{t_2}.$$
Equivalently, it sums
$$2F(n,K)=\sum_{i=1}^{n-K+1} \bigl(a_{t_1}^{(i)}+a_{t_2}^{(i)}\bigr),$$
where \(a_{t_1}^{(i)}\) and \(a_{t_2}^{(i)}\) are the two middle order statistics of the \(i\)-th window. Only at the very end is the result divided by \(2\), which guarantees an exact decimal ending in .0 or .5.
For \(1\le k\le 10\), we have \(\left\lfloor k/10000\right\rfloor+1=1\), and \(S(1)=2\). Therefore the first ten values are
$$\{S_2(1),\dots,S_2(10)\}=\{4,11,127,2403,941,3437,1640,2867,6554,9242\}.$$
After sorting, the window becomes
$$\{4,11,127,941,1640,2403,2867,3437,6554,9242\}.$$
The middle positions are \(5\) and \(6\), so
$$M(1,10)=\frac{1640+2403}{2}=\frac{4043}{2}=2021.5.$$
The doubled contribution is \(4043\), exactly the value used by the implementation when checking this sample window.
The C++, Python, and Java implementations follow the same pipeline. They first estimate a bound for the \(n\)-th prime and sieve only odd numbers, which is enough to stream primes in order without storing a full list of all candidates. As each prime arrives, the implementation computes the corresponding residue \(S(k)\), caches the early residues needed by the shifted term, and immediately forms the next \(S_2(k)\).
The current window is maintained by combining a circular buffer with a Fenwick tree over the value range \(0\) through \(20012\). Filling the first \(K\) values creates the initial multiset. Each later step removes the outgoing value, inserts the new one, and asks the Fenwick tree for the middle rank or the two middle ranks. The running sum is kept doubled, so no rounding is needed. The C++ implementation also verifies the sample medians and sample sums from the problem statement before evaluating the full instance; the Python and Java versions implement the same algorithmic idea with the same mathematics.
Let \(B\) be the sieve bound used for the \(n\)-th prime, and let \(V=20013\). Building the odd-only sieve costs \(O(B\log\log B)\) time and uses sieve storage proportional to \(B\). Streaming the sequence contributes one modular exponentiation per prime, and because the modulus is fixed and the exponent is reduced modulo \(10006\), this behaves as constant-cost arithmetic per term. The sliding-window part performs two Fenwick updates and one or two rank searches per window, each in \(O(\log V)\) time. Since \(V\) is fixed, the median-maintenance cost is \(O(n\log V)\) with very small constants, and the additional working memory is \(O(V+K)\) besides the sieve.
Die Folge ist definiert durch
$$S(k)=p_k^k \bmod 10007,\qquad S_2(k)=S(k)+S\left(\left\lfloor\frac{k}{10000}\right\rfloor+1\right),$$
wobei \(p_k\) die \(k\)-te Primzahl ist. Für jedes zusammenhängende Fenster \(S_2(i),S_2(i+1),\dots,S_2(i+K-1)\) sei \(M(i,i+K-1)\) der Median, also bei geradem \(K\) der Mittelwert der beiden mittleren Elemente. Gesucht ist
$$F(n,K)=\sum_{i=1}^{n-K+1} M(i,i+K-1).$$
Ein naiver Neuaufbau jedes Fensters wäre viel zu teuer. Die Lösung funktioniert nur deshalb schnell, weil sich die Folge online erzeugen lässt, alle Werte in einem kleinen festen Bereich liegen und Medianabfragen deshalb über Häufigkeiten statt über wiederholtes Sortieren beantwortet werden können.
Die Methode verbindet zwei Ideen: die Werte von \(S_2\) werden beim Durchlaufen der Primzahlen direkt erzeugt, und der Median eines Fensters wird als Ordnungsstatistik aus Präfixhäufigkeiten gewonnen.
Da \(10007\) prim ist, ist jede Primzahl \(p_k\neq 10007\) modulo \(10007\) invertierbar. Daher erlaubt der kleine Satz von Fermat, den Exponenten modulo
$$\varphi(10007)=10006$$
zu reduzieren. Außer im einen Spezialfall \(p_k=10007\) gilt also
$$p_k^k \bmod 10007 = p_k^{\,k \bmod 10006} \bmod 10007.$$
Damit wird jeder Term zu einer schnellen modularen Potenzierung, sobald die \(k\)-te Primzahl bekannt ist. Die Implementierungen schätzen dazu eine sichere obere Schranke für die \(n\)-te Primzahl und erzeugen die Primzahlen mit einem nur auf ungerade Zahlen beschränkten Sieb.
Aus der Definition folgt
$$0\le S(k)\le 10006.$$
Daher gilt auch
$$0\le S_2(k)=S(k)+S\left(\left\lfloor\frac{k}{10000}\right\rfloor+1\right)\le 20012.$$
Genau diese Schranke macht das Problem beherrschbar. Jeder Fensterwert liegt im festen Bereich
$$\{0,1,2,\dots,20012\},$$
also in einer Domäne der Größe \(V=20013\). Für den Zielwert \(n=10^7\) überschreitet der verschobene Index \(\left\lfloor k/10000\right\rfloor+1\) nie den Wert \(1001\); deshalb müssen nur diese frühen Folgenterme zwischengespeichert werden.
Für ein Fenster der Länge \(K\) sei \(f_v\) die Häufigkeit des Werts \(v\). Definiere die Präfixsummen
$$P(v)=\sum_{x=0}^{v} f_x.$$
Dann ist das \(t\)-kleinste Element genau der eindeutige Wert \(v\) mit
$$P(v-1) \lt t \le P(v).$$
Schreibt man die sortierten Fensterwerte als \(a_1\le a_2\le \cdots \le a_K\), dann liefern
$$t_1=\left\lfloor\frac{K+1}{2}\right\rfloor,\qquad t_2=\left\lfloor\frac{K+2}{2}\right\rfloor$$
die kompakte Medianformel
$$M=\frac{a_{t_1}+a_{t_2}}{2}.$$
Damit reduziert sich jede Medianabfrage auf das Finden von einer oder zwei Ordnungsstatistiken in einer Häufigkeitstabelle.
Beim Verschieben des Fensters um eine Position ändern sich nur zwei Elemente: ein ausgehender Wert verschwindet und ein neuer Wert kommt hinzu. In Häufigkeitsschreibweise bedeutet das
$$f_{v_{\text{out}}}\leftarrow f_{v_{\text{out}}}-1,\qquad f_{v_{\text{in}}}\leftarrow f_{v_{\text{in}}}+1.$$
Ein Fenwick-Baum speichert das Feld \((f_0,f_1,\dots,f_{20012})\), unterstützt beide Updates in \(O(\log V)\) und kann außerdem per binärer Präfixsuche den kleinsten Wert finden, dessen Präfixsumme einen Zielrang \(t\) erreicht. So kostet auch die Medianbestimmung pro Fenster nur \(O(\log V)\).
Für gerades \(K\) kann ein Median auf \(0.5\) enden. Anstatt mit Gleitkommazahlen zu arbeiten, summiert die Implementierung den verdoppelten Beitrag
$$2M=a_{t_1}+a_{t_2}.$$
Äquivalent dazu wird
$$2F(n,K)=\sum_{i=1}^{n-K+1} \bigl(a_{t_1}^{(i)}+a_{t_2}^{(i)}\bigr)$$
akkumuliert, wobei \(a_{t_1}^{(i)}\) und \(a_{t_2}^{(i)}\) die beiden mittleren Ordnungsstatistiken des \(i\)-ten Fensters bezeichnen. Erst ganz am Ende wird durch \(2\) geteilt, wodurch die Ausgabe exakt auf .0 oder .5 endet.
Für \(1\le k\le 10\) gilt \(\left\lfloor k/10000\right\rfloor+1=1\), und \(S(1)=2\). Daher sind die ersten zehn Werte
$$\{S_2(1),\dots,S_2(10)\}=\{4,11,127,2403,941,3437,1640,2867,6554,9242\}.$$
Sortiert ergibt das
$$\{4,11,127,941,1640,2403,2867,3437,6554,9242\}.$$
Die mittleren Positionen sind \(5\) und \(6\), also
$$M(1,10)=\frac{1640+2403}{2}=\frac{4043}{2}=2021.5.$$
Der verdoppelte Beitrag ist \(4043\), genau der Kontrollwert, den die Implementierung für dieses Beispiel verwendet.
Die C++-, Python- und Java-Implementierungen folgen derselben Pipeline. Zuerst wird eine Schranke für die \(n\)-te Primzahl geschätzt und ein Sieb nur über ungerade Zahlen aufgebaut. Damit lassen sich die Primzahlen der Reihe nach erzeugen, ohne alle Kandidaten explizit zu speichern. Wenn eine neue Primzahl eintrifft, berechnet die Implementierung sofort den zugehörigen Rest \(S(k)\), merkt sich die frühen Werte für den verschobenen Summanden und formt direkt den nächsten Wert \(S_2(k)\).
Das aktuelle Fenster wird mit einem Ringpuffer und einem Fenwick-Baum über dem Wertebereich \(0\) bis \(20012\) verwaltet. Nach dem Füllen der ersten \(K\) Werte ist das Startfenster komplett. Danach entfernt jeder Schritt den ausgehenden Wert, fügt den neuen Wert ein und fragt die mittlere Rangposition beziehungsweise die beiden mittleren Rangpositionen ab. Die laufende Summe bleibt dabei verdoppelt, sodass keine Rundung nötig ist. Die C++-Implementierung prüft vor dem Hauptlauf außerdem die Beispielmediane und Beispielsummenterme aus der Aufgabenstellung; Python und Java setzen dieselbe Idee mit derselben Mathematik um.
Sei \(B\) die verwendete Siebschranke für die \(n\)-te Primzahl und \(V=20013\). Das ungerade Sieb kostet \(O(B\log\log B)\) Zeit und Speicher proportional zu \(B\). Das Erzeugen der Folge liefert pro Primzahl genau eine modulare Potenzierung; wegen festem Modulus und Exponentenreduktion modulo \(10006\) ist das konstante Wortarithmetik pro Term. Der Sliding-Window-Teil benötigt pro Fenster zwei Fenwick-Updates und eine oder zwei Rangabfragen, jeweils in \(O(\log V)\). Da \(V\) fest ist, liegt der Median-Teil bei \(O(n\log V)\) mit sehr kleinen Konstanten, und der zusätzliche Arbeitsspeicher beträgt \(O(V+K)\) neben dem Sieb.
Dizi şu şekilde tanımlanır:
$$S(k)=p_k^k \bmod 10007,\qquad S_2(k)=S(k)+S\left(\left\lfloor\frac{k}{10000}\right\rfloor+1\right),$$
burada \(p_k\), \(k\)-ıncı asaldır. Her \(S_2(i),S_2(i+1),\dots,S_2(i+K-1)\) penceresi için \(M(i,i+K-1)\) medyan olsun; \(K\) çiftse bu, ortadaki iki değerin ortalamasıdır. Hesaplanmak istenen toplam
$$F(n,K)=\sum_{i=1}^{n-K+1} M(i,i+K-1)$$
şeklindedir. Her pencereyi yeniden sıralamak çok pahalı olurdu. Çözümün hızlı olmasının nedeni, dizinin çevrim içi üretilebilmesi, tüm değerlerin çok küçük sabit bir aralıkta kalması ve bu yüzden medyanın tekrar sıralama yerine frekanslardan çıkarılabilmesidir.
Yöntem iki gözleme dayanır: \(S_2\) terimleri asallar akarken doğrudan üretilebilir ve bir çoklu kümenin medyanı kümülatif frekanslardan bir sıralama istatistiği olarak bulunabilir.
\(10007\) asal olduğundan, \(p_k\neq 10007\) olan her asal \(10007\) modunda terslenebilir. Bu nedenle Fermat'ın küçük teoremi üssü
$$\varphi(10007)=10006$$
modunda küçültmeye izin verir. Yani tek istisna \(p_k=10007\) durumu dışında
$$p_k^k \bmod 10007 = p_k^{\,k \bmod 10006} \bmod 10007$$
yazabiliriz. Böylece \(k\)-ıncı asal bilindiğinde her terim hızlı modüler üs alma ile hesaplanır. C++, Python ve Java uygulamaları \(n\)-inci asal için güvenli bir üst sınır tahmin eder ve yalnızca tek sayıları içeren bir elekle asalları sırayla üretir.
Tanımdan
$$0\le S(k)\le 10006$$
olur. Dolayısıyla
$$0\le S_2(k)=S(k)+S\left(\left\lfloor\frac{k}{10000}\right\rfloor+1\right)\le 20012.$$
Asıl kolaylaştırıcı nokta budur. Her pencere değeri
$$\{0,1,2,\dots,20012\}$$
sabit kümesinin içindedir; bu kümenin boyutu sadece \(V=20013\) tür. Hedef örnek \(n=10^7\) için \(\left\lfloor k/10000\right\rfloor+1\) en fazla \(1001\) olur. Bu yüzden uygulama ikinci toplamdaki kaydırılmış terimi üretmek için yalnızca ilk \(1001\) dizi değerini saklar.
Uzunluğu \(K\) olan bir pencere için \(f_v\), değeri \(v\) olan eleman sayısı olsun. Kümülatif frekansları
$$P(v)=\sum_{x=0}^{v} f_x$$
şeklinde tanımlayalım. O zaman \(t\)-inci küçük eleman,
$$P(v-1) \lt t \le P(v)$$
eşitsizliğini sağlayan tek \(v\) değeridir. Sıralanmış pencere değerleri \(a_1\le a_2\le \cdots \le a_K\) ise
$$t_1=\left\lfloor\frac{K+1}{2}\right\rfloor,\qquad t_2=\left\lfloor\frac{K+2}{2}\right\rfloor$$
seçilerek medyan tek formülde yazılır:
$$M=\frac{a_{t_1}+a_{t_2}}{2}.$$
Böylece her pencere için medyan bulma işi, frekans tablosunda bir ya da iki sıralama istatistiği bulmaya indirgenir.
Pencere bir adım kayınca sadece iki eleman değişir: biri çıkar, biri girer. Frekans cinsinden bu
$$f_{v_{\text{out}}}\leftarrow f_{v_{\text{out}}}-1,\qquad f_{v_{\text{in}}}\leftarrow f_{v_{\text{in}}}+1$$
demektir. Fenwick ağacı \((f_0,f_1,\dots,f_{20012})\) dizisini tutar, her iki güncellemeyi \(O(\log V)\) sürede yapar ve ayrıca önek toplamı istenen sıraya ilk ulaştıran değeri de bulabilir. Böylece pencere başına medyan çıkarma maliyeti de \(O(\log V)\) olur.
\(K\) çift olduğunda medyan \(0.5\) ile bitebilir. Kayan nokta kullanmak yerine uygulama iki kat katkıyı toplar:
$$2M=a_{t_1}+a_{t_2}.$$
Başka bir deyişle
$$2F(n,K)=\sum_{i=1}^{n-K+1} \bigl(a_{t_1}^{(i)}+a_{t_2}^{(i)}\bigr)$$
bir tam sayı olarak biriktirilir. Burada \(a_{t_1}^{(i)}\) ve \(a_{t_2}^{(i)}\), \(i\)-inci pencerenin iki orta sıralama istatistiğidir. En sonda yalnızca ikiye bölünür ve sonuç tam olarak .0 ya da .5 ile yazdırılır.
\(1\le k\le 10\) için \(\left\lfloor k/10000\right\rfloor+1=1\) ve \(S(1)=2\) olur. Bu yüzden ilk on değer
$$\{S_2(1),\dots,S_2(10)\}=\{4,11,127,2403,941,3437,1640,2867,6554,9242\}$$
şeklindedir. Sıralayınca
$$\{4,11,127,941,1640,2403,2867,3437,6554,9242\}$$
elde edilir. Ortadaki konumlar \(5\) ve \(6\) olduğundan
$$M(1,10)=\frac{1640+2403}{2}=\frac{4043}{2}=2021.5.$$
İkiye katlanmış katkı \(4043\) olur; bu da uygulamanın bu örnek için kullandığı kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları aynı akışı izler. Önce \(n\)-inci asal için bir üst sınır tahmin edilir ve yalnızca tek sayıları tutan bir elek kurulur. Böylece asallar sırayla akıtılır; tüm adayları veya tüm asalları ayrı ayrı depolamak gerekmez. Yeni bir asal geldiğinde uygulama hemen ilgili \(S(k)\) kalıntısını hesaplar, kaydırılmış terim için gereken erken değerleri saklar ve bir sonraki \(S_2(k)\) değerini anında oluşturur.
Güncel pencere, dairesel bir tampon ile \(0\) ila \(20012\) aralığında çalışan bir Fenwick ağacının birleşimiyle tutulur. İlk \(K\) değer doldurulunca başlangıç penceresi hazır olur. Sonraki her adımda çıkan değer silinir, yeni değer eklenir ve ortadaki sıra ya da iki orta sıra Fenwick üzerinden bulunur. Toplam daima ikiyle çarpılmış halde tutulduğu için yuvarlama sorunu yoktur. C++ uygulaması ayrıca tam örneği hesaplamadan önce problem ifadesindeki örnek medyanları ve örnek toplamları doğrular; Python ve Java sürümleri aynı matematiksel fikri uygular.
\(B\), \(n\)-inci asal için kullanılan elek üst sınırı ve \(V=20013\) olsun. Tek sayılı elek \(O(B\log\log B)\) zamanda kurulur ve \(B\) ile orantılı depolama kullanır. Diziyi akıtarak üretme aşaması her asal için bir modüler üs alma içerir; modül sabit ve üs \(10006\) modunda küçültüldüğü için bu parça terim başına sabit maliyetli sözcük aritmetiği gibi davranır. Kayan pencere kısmı ise her pencere için iki Fenwick güncellemesi ve bir ya da iki sıra araması yapar; bunların her biri \(O(\log V)\) sürer. \(V\) sabit olduğundan medyan bakım maliyeti çok küçük sabitlerle \(O(n\log V)\) olur ve elek dışında ek bellek gereksinimi \(O(V+K)\) düzeyindedir.
La sucesión se define por
$$S(k)=p_k^k \bmod 10007,\qquad S_2(k)=S(k)+S\left(\left\lfloor\frac{k}{10000}\right\rfloor+1\right),$$
donde \(p_k\) es el \(k\)-ésimo primo. Para cada ventana contigua \(S_2(i),S_2(i+1),\dots,S_2(i+K-1)\), sea \(M(i,i+K-1)\) su mediana, entendida como el promedio de los dos valores centrales cuando \(K\) es par. La cantidad pedida es
$$F(n,K)=\sum_{i=1}^{n-K+1} M(i,i+K-1).$$
Recalcular la mediana ordenando cada ventana sería demasiado lento. La estrategia funciona porque la sucesión puede generarse en flujo, todos los valores caen en un intervalo fijo muy pequeño y, por tanto, las medianas se recuperan a partir de frecuencias en vez de volver a ordenar cada bloque.
La solución junta dos observaciones: los términos de \(S_2\) se pueden producir en línea mientras se recorren los primos, y la mediana de un multiconjunto puede obtenerse como una estadística de orden a partir de frecuencias acumuladas.
Como \(10007\) es primo, cualquier primo \(p_k\neq 10007\) es invertible módulo \(10007\). Por ello, el pequeño teorema de Fermat permite reducir el exponente módulo
$$\varphi(10007)=10006.$$
Salvo en el único caso \(p_k=10007\), podemos escribir
$$p_k^k \bmod 10007 = p_k^{\,k \bmod 10006} \bmod 10007.$$
Así, cada término se convierte en una exponenciación modular rápida una vez conocido el \(k\)-ésimo primo. Las implementaciones estiman una cota superior segura para el \(n\)-ésimo primo y usan una criba solo de impares para enumerarlos en orden.
Por definición,
$$0\le S(k)\le 10006.$$
Entonces también se cumple
$$0\le S_2(k)=S(k)+S\left(\left\lfloor\frac{k}{10000}\right\rfloor+1\right)\le 20012.$$
Esta cota es el punto decisivo. Cada valor de la ventana pertenece al dominio fijo
$$\{0,1,2,\dots,20012\},$$
de tamaño apenas \(V=20013\). Para la instancia objetivo \(n=10^7\), el índice desplazado \(\left\lfloor k/10000\right\rfloor+1\) nunca supera \(1001\), así que basta con guardar esos primeros valores para reconstruir el segundo sumando.
En una ventana de longitud \(K\), sea \(f_v\) el número de apariciones del valor \(v\). Definimos las frecuencias acumuladas
$$P(v)=\sum_{x=0}^{v} f_x.$$
El \(t\)-ésimo menor valor es el único \(v\) que verifica
$$P(v-1) \lt t \le P(v).$$
Si los elementos ordenados de la ventana son \(a_1\le a_2\le \cdots \le a_K\), entonces
$$t_1=\left\lfloor\frac{K+1}{2}\right\rfloor,\qquad t_2=\left\lfloor\frac{K+2}{2}\right\rfloor$$
y la mediana queda expresada como
$$M=\frac{a_{t_1}+a_{t_2}}{2}.$$
Así, cada consulta de mediana se reduce a encontrar una o dos estadísticas de orden dentro de una tabla de frecuencias.
Al mover la ventana una posición, solo cambian dos elementos: sale uno y entra otro. En términos de frecuencias, eso significa
$$f_{v_{\text{out}}}\leftarrow f_{v_{\text{out}}}-1,\qquad f_{v_{\text{in}}}\leftarrow f_{v_{\text{in}}}+1.$$
Un árbol de Fenwick almacena \((f_0,f_1,\dots,f_{20012})\), permite ambos cambios en \(O(\log V)\) y también puede buscar el menor valor cuya suma prefija alcance un rango objetivo \(t\). Por eso la extracción de la mediana también cuesta \(O(\log V)\) por ventana.
Cuando \(K\) es par, la mediana puede terminar en \(0.5\). En lugar de acumular números en coma flotante, la implementación suma la contribución doblada
$$2M=a_{t_1}+a_{t_2}.$$
Equivalente a ello, se acumula
$$2F(n,K)=\sum_{i=1}^{n-K+1} \bigl(a_{t_1}^{(i)}+a_{t_2}^{(i)}\bigr),$$
donde \(a_{t_1}^{(i)}\) y \(a_{t_2}^{(i)}\) son los dos valores centrales de la ventana \(i\). Solo al final se divide entre \(2\), lo que garantiza una salida exacta con terminación .0 o .5.
Para \(1\le k\le 10\), se cumple \(\left\lfloor k/10000\right\rfloor+1=1\), y además \(S(1)=2\). Por tanto, los diez primeros valores son
$$\{S_2(1),\dots,S_2(10)\}=\{4,11,127,2403,941,3437,1640,2867,6554,9242\}.$$
Ordenados, quedan
$$\{4,11,127,941,1640,2403,2867,3437,6554,9242\}.$$
Las posiciones centrales son la \(5\) y la \(6\), así que
$$M(1,10)=\frac{1640+2403}{2}=\frac{4043}{2}=2021.5.$$
La contribución doblada es \(4043\), exactamente el valor de comprobación que usa la implementación para esta ventana de ejemplo.
Las implementaciones en C++, Python y Java siguen la misma cadena de trabajo. Primero estiman una cota para el \(n\)-ésimo primo y construyen una criba limitada a números impares. Eso basta para ir generando los primos en orden sin mantener una lista completa de todos los candidatos. Cada vez que aparece un nuevo primo, la implementación calcula el residuo \(S(k)\), guarda los primeros residuos que hacen falta para el término desplazado y forma inmediatamente el siguiente valor \(S_2(k)\).
La ventana actual se mantiene con un búfer circular y un árbol de Fenwick sobre el rango \(0\) a \(20012\). Al cargar los primeros \(K\) valores se obtiene la ventana inicial. Después, en cada paso se elimina el valor saliente, se inserta el nuevo y se consulta el rango central o los dos rangos centrales en el árbol. La suma acumulada se mantiene doblada para evitar cualquier redondeo. La versión en C++ también verifica las medianas y sumas de muestra dadas en el enunciado antes de evaluar el caso principal; las versiones en Python y Java implementan la misma idea matemática.
Sea \(B\) la cota usada en la criba para el \(n\)-ésimo primo, y sea \(V=20013\). Construir la criba de impares cuesta \(O(B\log\log B)\) tiempo y almacenamiento proporcional a \(B\). La generación en flujo aporta una exponenciación modular por primo; como el módulo es fijo y el exponente se reduce módulo \(10006\), ese trabajo se comporta como costo constante por término. La parte de ventana deslizante realiza dos actualizaciones del árbol de Fenwick y una o dos búsquedas de rango por ventana, cada una en \(O(\log V)\). Como \(V\) es fijo, el mantenimiento de medianas cuesta \(O(n\log V)\) con constantes muy pequeñas, y la memoria adicional es \(O(V+K)\) aparte de la criba.
题目定义了序列
$$S(k)=p_k^k \bmod 10007,\qquad S_2(k)=S(k)+S\left(\left\lfloor\frac{k}{10000}\right\rfloor+1\right),$$
其中 \(p_k\) 表示第 \(k\) 个素数。对每个连续窗口 \(S_2(i),S_2(i+1),\dots,S_2(i+K-1)\)，记 \(M(i,i+K-1)\) 为该窗口的中位数；如果 \(K\) 为偶数，中位数取中间两个数的平均值。目标是计算
$$F(n,K)=\sum_{i=1}^{n-K+1} M(i,i+K-1).$$
如果对每个窗口都重新排序，再取中位数，那么在真实规模下完全不可行。真正可行的做法依赖于三点：序列可以按顺序流式生成，所有值都落在一个很小的固定范围内，因此窗口中位数可以通过频率统计得到，而不必反复排序。
这道题的核心不是“如何定义中位数”，而是“如何在超大滑动窗口中持续维护中位数”。实现中的数学结构可以拆成两部分：先高效生成 \(S_2(k)\)，再把窗口中位数改写成频率上的顺序统计量问题。
因为 \(10007\) 是素数，所以除了 \(p_k=10007\) 这一种特殊情况以外，所有 \(p_k\) 都与 \(10007\) 互素。于是可以使用费马小定理，把指数按
$$\varphi(10007)=10006$$
进行化简。也就是说，当 \(p_k\neq 10007\) 时，
$$p_k^k \bmod 10007 = p_k^{\,k \bmod 10006} \bmod 10007.$$
这样一来，只要按顺序得到第 \(k\) 个素数，每一项 \(S(k)\) 都只需要一次快速幂。C++、Python 和 Java 实现都先估计第 \(n\) 个素数的一个安全上界，再用只处理奇数的筛法按顺序生成素数，从而避免更昂贵的数据组织。
由定义立刻得到
$$0\le S(k)\le 10006.$$
因此
$$0\le S_2(k)=S(k)+S\left(\left\lfloor\frac{k}{10000}\right\rfloor+1\right)\le 20012.$$
这一步是整题最关键的结构性简化。因为所有窗口元素都属于固定集合
$$\{0,1,2,\dots,20012\},$$
其大小只有 \(V=20013\)，所以我们不必维护“有序窗口”，只要维护这个有限值域上的频率分布即可。对于目标实例 \(n=10^7\)，偏移项中的索引 \(\left\lfloor k/10000\right\rfloor+1\) 最大只有 \(1001\)，因此实现只需缓存前 \(1001\) 个 \(S(k)\) 值，就能持续构造后面的全部 \(S_2(k)\)。
设当前窗口长度为 \(K\)，并令 \(f_v\) 表示数值 \(v\) 在窗口中出现的次数。定义前缀计数
$$P(v)=\sum_{x=0}^{v} f_x.$$
那么第 \(t\) 小的值，就是满足下式的唯一 \(v\)：
$$P(v-1) \lt t \le P(v).$$
如果把窗口元素从小到大写成 \(a_1\le a_2\le \cdots \le a_K\)，则令
$$t_1=\left\lfloor\frac{K+1}{2}\right\rfloor,\qquad t_2=\left\lfloor\frac{K+2}{2}\right\rfloor,$$
就可以统一写成
$$M=\frac{a_{t_1}+a_{t_2}}{2}.$$
当 \(K\) 为奇数时，\(t_1=t_2\)，这就是通常的中间元素；当 \(K\) 为偶数时，它正好变成两个中间元素的平均值。因此，中位数问题被转换成了“在频率分布中找第 \(t\) 小元素”的问题。
窗口每向右移动一次，只会发生两件事：最左端旧值离开，最右端新值进入。用频率表示，这就是
$$f_{v_{\text{out}}}\leftarrow f_{v_{\text{out}}}-1,\qquad f_{v_{\text{in}}}\leftarrow f_{v_{\text{in}}}+1.$$
实现用 Fenwick 树维护 \((f_0,f_1,\dots,f_{20012})\)。这种结构既能在 \(O(\log V)\) 时间内完成单点增减，也能通过前缀和搜索找到“前缀和第一次达到目标排名 \(t\)”的数值。因此，窗口每次移动之后，重新得到中位数也只需要 \(O(\log V)\) 时间。
当 \(K\) 为偶数时，中位数可能以 \(0.5\) 结尾。如果直接用浮点数累计，虽然概念上简单，但没有必要，而且会引入格式化处理。实现采用的做法是始终累计两倍的贡献：
$$2M=a_{t_1}+a_{t_2}.$$
于是总和实际上维护的是
$$2F(n,K)=\sum_{i=1}^{n-K+1} \bigl(a_{t_1}^{(i)}+a_{t_2}^{(i)}\bigr),$$
其中 \(a_{t_1}^{(i)}\) 和 \(a_{t_2}^{(i)}\) 是第 \(i\) 个窗口的中间顺序统计量。这样整个运行过程都只做整数运算。最后再除以 \(2\)，并根据奇偶性输出 .0 或 .5 即可。
对 \(1\le k\le 10\)，都有 \(\left\lfloor k/10000\right\rfloor+1=1\)，并且 \(S(1)=2\)。因此前十个值为
$$\{S_2(1),\dots,S_2(10)\}=\{4,11,127,2403,941,3437,1640,2867,6554,9242\}.$$
排序后得到
$$\{4,11,127,941,1640,2403,2867,3437,6554,9242\}.$$
中间位置是第 \(5\) 和第 \(6\) 个元素，所以
$$M(1,10)=\frac{1640+2403}{2}=\frac{4043}{2}=2021.5.$$
也就是说，这个窗口对“两倍总和”的贡献是 \(4043\)。这与实现里使用的样例校验完全一致，也很好地展示了为什么保存两倍结果是自然的。
C++、Python 和 Java 实现的总体流程是相同的。首先，它们估计第 \(n\) 个素数的上界，然后建立一个只筛奇数的素数筛。这样就可以按顺序流式得到素数，而不用维护一个巨大的候选集合。每得到一个新的素数，就立刻计算相应的 \(S(k)\)，把构造偏移项所需的早期值缓存起来，并直接形成当前的 \(S_2(k)\)。
窗口本身由两部分共同维护：一个循环缓冲区负责知道“谁要离开窗口”，一个 Fenwick 树负责维护整个值域上的频率。先填满前 \(K\) 个值形成初始窗口，然后每一步都删除旧值、加入新值，再从 Fenwick 树中取出中间排名或两个中间排名。整个累加过程始终保存为“两倍总和”，因此不存在精度损失。C++ 实现还会先检查题目给出的样例中位数和样例求和值，再继续计算最终实例；Python 和 Java 版本实现的是同一套数学思路。
设 \(B\) 为用于覆盖第 \(n\) 个素数的筛上界，\(V=20013\) 为值域大小。只筛奇数的筛法需要 \(O(B\log\log B)\) 时间，并使用与 \(B\) 成比例的筛存储。序列生成阶段对每个素数进行一次模幂计算；由于模数固定且指数已按 \(10006\) 取模化简，这部分在机器字模型下可以视作单项常数成本。滑动窗口阶段每次移动要做两次 Fenwick 更新以及一次或两次顺序统计量搜索，每次都是 \(O(\log V)\)。因为 \(V\) 是固定常数，所以中位数维护部分总体是 \(O(n\log V)\)，常数很小；除筛本身外，额外工作内存为 \(O(V+K)\)。
Последовательность задается формулами
$$S(k)=p_k^k \bmod 10007,\qquad S_2(k)=S(k)+S\left(\left\lfloor\frac{k}{10000}\right\rfloor+1\right),$$
где \(p_k\) обозначает \(k\)-е простое число. Для каждого непрерывного окна \(S_2(i),S_2(i+1),\dots,S_2(i+K-1)\) пусть \(M(i,i+K-1)\) будет его медианой; при четном \(K\) это среднее двух центральных элементов. Требуется вычислить
$$F(n,K)=\sum_{i=1}^{n-K+1} M(i,i+K-1).$$
Если для каждого окна заново сортировать элементы, задача становится слишком тяжелой. Реальное решение опирается на то, что значения можно генерировать по одному, все они лежат в небольшом фиксированном диапазоне, а значит медиану можно извлекать по частотам, не поддерживая явную сортировку окна.
В основе метода две идеи: сначала дешево строится поток значений \(S_2(k)\), а затем медиана окна выражается через порядковые статистики, найденные по накопленным частотам.
Поскольку \(10007\) является простым числом, любой простой \(p_k\neq 10007\) обратим по модулю \(10007\). Поэтому по малой теореме Ферма показатель можно сократить по модулю
$$\varphi(10007)=10006.$$
Иначе говоря, за исключением единственного случая \(p_k=10007\), верно
$$p_k^k \bmod 10007 = p_k^{\,k \bmod 10006} \bmod 10007.$$
Значит, после получения очередного простого числа каждый член \(S(k)\) считается одной быстрой модульной степенью. Реализации на C++, Python и Java сначала оценивают безопасную верхнюю границу для \(n\)-го простого, а затем используют решето только по нечетным числам, чтобы перечислять простые по порядку.
Из определения сразу следует
$$0\le S(k)\le 10006.$$
Следовательно,
$$0\le S_2(k)=S(k)+S\left(\left\lfloor\frac{k}{10000}\right\rfloor+1\right)\le 20012.$$
Именно это ограничение делает задачу удобной. Любой элемент окна принадлежит фиксированному множеству
$$\{0,1,2,\dots,20012\},$$
размер которого равен всего \(V=20013\). Для целевого случая \(n=10^7\) смещенный индекс \(\left\lfloor k/10000\right\rfloor+1\) никогда не превосходит \(1001\), поэтому достаточно запомнить только первые \(1001\) значения \(S(k)\), чтобы строить второе слагаемое для всех последующих позиций.
Пусть окно имеет длину \(K\), а \(f_v\) обозначает число вхождений значения \(v\) в это окно. Введем префиксные суммы
$$P(v)=\sum_{x=0}^{v} f_x.$$
Тогда \(t\)-й по величине элемент есть единственное значение \(v\), удовлетворяющее
$$P(v-1) \lt t \le P(v).$$
Если упорядоченные элементы окна обозначить как \(a_1\le a_2\le \cdots \le a_K\), то при
$$t_1=\left\lfloor\frac{K+1}{2}\right\rfloor,\qquad t_2=\left\lfloor\frac{K+2}{2}\right\rfloor$$
медиана записывается в единой форме
$$M=\frac{a_{t_1}+a_{t_2}}{2}.$$
При нечетном \(K\) оба индекса совпадают, а при четном дают два центральных значения. Поэтому задача о медиане сводится к поиску одной или двух порядковых статистик в таблице частот.
При сдвиге окна на один шаг изменяются только два элемента: один уходит, другой приходит. В терминах частот это
$$f_{v_{\text{out}}}\leftarrow f_{v_{\text{out}}}-1,\qquad f_{v_{\text{in}}}\leftarrow f_{v_{\text{in}}}+1.$$
Дерево Фенвика хранит массив \((f_0,f_1,\dots,f_{20012})\), выполняет оба обновления за \(O(\log V)\) и, кроме того, умеет находить минимальное значение, у которого префиксная сумма впервые достигает нужного ранга \(t\). Поэтому и обновление окна, и повторное извлечение медианы выполняются за \(O(\log V)\).
Когда \(K\) четно, медиана может оканчиваться на \(0.5\). Чтобы не использовать вещественную арифметику, реализация суммирует удвоенный вклад
$$2M=a_{t_1}+a_{t_2}.$$
Эквивалентно поддерживается сумма
$$2F(n,K)=\sum_{i=1}^{n-K+1} \bigl(a_{t_1}^{(i)}+a_{t_2}^{(i)}\bigr),$$
где \(a_{t_1}^{(i)}\) и \(a_{t_2}^{(i)}\) обозначают центральные порядковые статистики \(i\)-го окна. Вся работа идет в целых числах, а деление на \(2\) и выбор окончания .0 или .5 происходят только при выводе.
Для \(1\le k\le 10\) имеем \(\left\lfloor k/10000\right\rfloor+1=1\), а также \(S(1)=2\). Значит, первые десять значений равны
$$\{S_2(1),\dots,S_2(10)\}=\{4,11,127,2403,941,3437,1640,2867,6554,9242\}.$$
После сортировки получаем
$$\{4,11,127,941,1640,2403,2867,3437,6554,9242\}.$$
Центральные позиции здесь \(5\) и \(6\), поэтому
$$M(1,10)=\frac{1640+2403}{2}=\frac{4043}{2}=2021.5.$$
Удвоенный вклад равен \(4043\), и именно это значение используется реализацией при проверке данного образца.
Реализации на C++, Python и Java устроены одинаково по сути. Сначала оценивается верхняя граница для \(n\)-го простого и строится решето только по нечетным числам. Этого достаточно, чтобы получать простые по порядку без хранения громоздкой структуры кандидатов. Как только появляется очередное простое, реализация сразу вычисляет соответствующий остаток \(S(k)\), сохраняет ранние значения, необходимые для смещенного слагаемого, и немедленно формирует текущее \(S_2(k)\).
Само окно поддерживается комбинацией циклического буфера и дерева Фенвика на диапазоне от \(0\) до \(20012\). После заполнения первых \(K\) значений получается стартовое окно. На каждом следующем шаге старое значение удаляется, новое вставляется, а затем дерево возвращает центральный ранг или два центральных ранга. Бегущая сумма хранится в удвоенном виде, поэтому никаких ошибок округления не возникает. Реализация на C++ дополнительно сверяет результаты на выборочных медианах и выборочных суммах из условия, а версии на Python и Java реализуют ту же математическую схему.
Пусть \(B\) обозначает верхнюю границу решета для \(n\)-го простого, а \(V=20013\) — размер диапазона значений. Построение решета по нечетным требует \(O(B\log\log B)\) времени и хранения, пропорционального \(B\). Генерация последовательности добавляет по одной модульной степени на каждый простой; поскольку модуль фиксирован, а показатель сокращается по модулю \(10006\), эту часть можно считать константной по стоимости на один член. Скользящее окно для каждой позиции выполняет два обновления дерева Фенвика и один или два поиска порядковой статистики, каждый за \(O(\log V)\). Так как \(V\) фиксировано, поддержание медиан имеет трудоемкость \(O(n\log V)\) с очень малыми константами, а дополнительная рабочая память вне решета равна \(O(V+K)\).
تُعرَّف المتتالية بالعلاقتين
$$S(k)=p_k^k \bmod 10007,\qquad S_2(k)=S(k)+S\left(\left\lfloor\frac{k}{10000}\right\rfloor+1\right),$$
حيث \(p_k\) هو العدد الأولي رقم \(k\). ولكل نافذة متصلة \(S_2(i),S_2(i+1),\dots,S_2(i+K-1)\) نرمز إلى وسيطها بـ \(M(i,i+K-1)\)، وإذا كان \(K\) زوجيًا فالوسيط هو متوسط القيمتين الوسطيتين. المطلوب حساب
$$F(n,K)=\sum_{i=1}^{n-K+1} M(i,i+K-1).$$
إعادة فرز كل نافذة على حدة غير عملية إطلاقًا عند القيم الحقيقية للمسألة. والحل السريع ممكن فقط لأن عناصر المتتالية يمكن توليدها تدريجيًا، وكل قيمة تقع داخل مجال ثابت صغير جدًا، ولذلك يمكن استخراج الوسيط من تكرارات القيم بدل إعادة الفرز في كل مرة.
تعتمد الفكرة على شقين متكاملين: توليد قيم \(S_2(k)\) بكلفة منخفضة أثناء المرور على الأعداد الأولية، ثم تحويل مسألة الوسيط في النافذة المنزلقة إلى مسألة إيجاد رتب ترتيبية انطلاقًا من المجاميع التراكمية للتكرارات.
بما أن \(10007\) عدد أولي، فإن كل عدد أولي \(p_k\neq 10007\) يكون قابلاً للعكس بترديد \(10007\). لذلك تسمح مبرهنة فيرما الصغرى باختزال الأس بترديد
$$\varphi(10007)=10006.$$
أي إنه، باستثناء الحالة الوحيدة \(p_k=10007\)، نستطيع كتابة
$$p_k^k \bmod 10007 = p_k^{\,k \bmod 10006} \bmod 10007.$$
وهذا يعني أن كل حد من حدود \(S(k)\) يحتاج فقط إلى أسٍّ معياري سريع بعد معرفة العدد الأولي رقم \(k\). وتقوم تطبيقات C++ وPython وJava بتقدير حد علوي آمن للعدد الأولي رقم \(n\)، ثم تستخدم غربالًا يمر على الأعداد الفردية فقط لتوليد الأعداد الأولية بترتيبها الطبيعي.
من التعريف نحصل مباشرة على
$$0\le S(k)\le 10006.$$
ومن ثم
$$0\le S_2(k)=S(k)+S\left(\left\lfloor\frac{k}{10000}\right\rfloor+1\right)\le 20012.$$
هذه الملاحظة هي قلب الحل. فجميع قيم النافذة تنتمي إلى المجال الثابت
$$\{0,1,2,\dots,20012\},$$
وحجمه لا يتجاوز \(V=20013\). وفي الحالة المستهدفة \(n=10^7\)، فإن الفهرس المزاح \(\left\lfloor k/10000\right\rfloor+1\) لا يتجاوز \(1001\)، لذلك يكفي حفظ القيم الأولى من \(S(k)\) حتى هذا الحد من أجل بناء الحد الثاني في \(S_2(k)\) طوال التنفيذ.
لنفرض أن طول النافذة هو \(K\)، وأن \(f_v\) يساوي عدد مرات ظهور القيمة \(v\) داخل النافذة. نعرّف المجاميع التراكمية
$$P(v)=\sum_{x=0}^{v} f_x.$$
عندئذٍ تكون القيمة ذات الرتبة \(t\) هي القيمة الوحيدة \(v\) التي تحقق
$$P(v-1) \lt t \le P(v).$$
وإذا كتبنا عناصر النافذة بعد الترتيب على صورة \(a_1\le a_2\le \cdots \le a_K\)، فإن اختيار
$$t_1=\left\lfloor\frac{K+1}{2}\right\rfloor,\qquad t_2=\left\lfloor\frac{K+2}{2}\right\rfloor$$
يعطينا الصيغة الموحدة
$$M=\frac{a_{t_1}+a_{t_2}}{2}.$$
وعندما يكون \(K\) فرديًا يتطابق الرقمان، أما عندما يكون زوجيًا فهما يمثلان القيمتين الوسطيتين. وهكذا تصبح مهمة إيجاد الوسيط مجرد إيجاد عنصر أو عنصرين من عناصر الرتبة المحددة داخل توزيع التكرارات.
كل انتقال للنافذة خطوة واحدة إلى اليمين يغيّر عنصرين فقط: عنصر يخرج وعنصر جديد يدخل. وبصيغة التكرارات يصبح ذلك
$$f_{v_{\text{out}}}\leftarrow f_{v_{\text{out}}}-1,\qquad f_{v_{\text{in}}}\leftarrow f_{v_{\text{in}}}+1.$$
تُخزَّن القيم \((f_0,f_1,\dots,f_{20012})\) داخل شجرة Fenwick، وهي تسمح بالتحديثين في زمن \(O(\log V)\)، كما تسمح بالبحث عن أصغر قيمة يصل عندها المجموع التراكمي إلى رتبة مطلوبة \(t\). لذلك تبقى كلفة تحديث النافذة واستخراج وسيطها بعد كل حركة مساوية لـ \(O(\log V)\).
إذا كان \(K\) زوجيًا فقد يكون الوسيط منتهيًا بـ \(0.5\). ولتجنّب أي حسابات عائمة، تقوم الخوارزمية بتجميع المساهمة المضاعفة
$$2M=a_{t_1}+a_{t_2}.$$
وبصيغة كلية فهي تحافظ على
$$2F(n,K)=\sum_{i=1}^{n-K+1} \bigl(a_{t_1}^{(i)}+a_{t_2}^{(i)}\bigr),$$
حيث \(a_{t_1}^{(i)}\) و\(a_{t_2}^{(i)}\) هما القيمتان الوسطيتان في النافذة رقم \(i\). وبهذا تبقى جميع العمليات صحيحة على الأعداد الصحيحة فقط، ثم يجري القسمة على \(2\) في النهاية مع اختيار اللاحقة .0 أو .5 بدقة تامة.
عندما \(1\le k\le 10\)، يكون \(\left\lfloor k/10000\right\rfloor+1=1\)، كما أن \(S(1)=2\). لذلك تكون القيم العشر الأولى
$$\{S_2(1),\dots,S_2(10)\}=\{4,11,127,2403,941,3437,1640,2867,6554,9242\}.$$
وبعد الترتيب نحصل على
$$\{4,11,127,941,1640,2403,2867,3437,6554,9242\}.$$
الموضعان الأوسطان هما \(5\) و\(6\)، ومن ثم
$$M(1,10)=\frac{1640+2403}{2}=\frac{4043}{2}=2021.5.$$
إذن المساهمة المضاعفة لهذه النافذة هي \(4043\)، وهو بالضبط مقدار التحقق الذي تستخدمه الخوارزمية لهذا المثال.
تتبع تطبيقات C++ وPython وJava المسار نفسه من حيث الجوهر. فهي تبدأ بتقدير حد علوي للعدد الأولي رقم \(n\)، ثم تبني غربالًا للأعداد الفردية فقط. وهذا يكفي لتوليد الأعداد الأولية بالتسلسل من غير الحاجة إلى بنية ضخمة تحتفظ بجميع المرشحات. وكلما ظهر عدد أولي جديد، تحسب الخوارزمية مباشرة القيمة الموافقة لـ \(S(k)\)، وتخزن القيم المبكرة اللازمة للحد المزاح، ثم تكوّن فورًا القيمة الحالية لـ \(S_2(k)\).
أما النافذة الحالية فتُدار بواسطة مخزن دائري لمعرفة العنصر الخارج، مع شجرة Fenwick لحفظ التكرارات على المجال من \(0\) إلى \(20012\). بعد إدخال أول \(K\) عنصرًا نحصل على النافذة الابتدائية. وبعد ذلك يحذف كل انتقال القيمة الخارجة، ويضيف القيمة الجديدة، ثم يطلب من شجرة Fenwick الرتبة الوسطى أو الرتبتين الوسطيتين. ويُحفظ المجموع الجاري في صورة مضاعفة، لذلك لا توجد أي مشكلة تقريب. كما أن تنفيذ C++ يتحقق أولًا من عينات الوسيط وعينات المجموع المذكورة في نص المسألة، بينما تطبق نسختا Python وJava الفكرة الرياضية نفسها.
لنرمز بـ \(B\) إلى الحد الأعلى للغربال الذي يغطي العدد الأولي رقم \(n\)، ولْيكن \(V=20013\) هو حجم مجال القيم. بناء غربال الأعداد الفردية يحتاج إلى زمن \(O(B\log\log B)\) وإلى تخزين يتناسب مع \(B\). ويضيف توليد المتتالية عملية أسٍّ معياري واحدة لكل عدد أولي؛ وبما أن الترديد ثابت والأس مخفض بترديد \(10006\)، فإن هذا الجزء يتصرف ككلفة ثابتة لكل حد. أما مرحلة النافذة المنزلقة فتجري تحديثين في شجرة Fenwick وبحثًا واحدًا أو بحثين عن رتب ترتيبية لكل نافذة، وكل عملية منها تكلف \(O(\log V)\). ولأن \(V\) ثابت، فإن كلفة صيانة الوسائط هي \(O(n\log V)\) مع ثوابت صغيرة جدًا، بينما تكون الذاكرة الإضافية خارج الغربال من رتبة \(O(V+K)\).