Let \(p_0=2,p_1=3,\dots,p_{k-1}\) be the first \(k\) primes. We choose \(n\) indices \(a_1,\dots,a_n\in\{0,\dots,k-1\}\) and define the score
$$S=\sum_{i=1}^{n} p_{a_i}.$$
The admissibility condition is
$$\sum_{i=1}^{n} a_i\equiv 0 \pmod{k}.$$
If the congruence were ignored, the best possible choice would be to take the largest available prime \(p_{k-1}\) every time. The real task is therefore to understand the smallest penalty needed to correct the residue class of the index sum while keeping the total score as large as possible.
The C++, Python, and Java implementations all convert the constrained maximization into a minimum-loss problem on residue classes modulo \(k\).
Write
$$P=p_{k-1}.$$
If every term were chosen to be \(P\), the score would simply be
$$nP.$$
Any legal solution can only differ from this ideal by replacing some copies of \(P\) with smaller primes from the same list.
For every selected index define the deficit
$$d_i=(k-1)-a_i,\qquad 0\le d_i\le k-1.$$
Then \(d_i=0\) means that the largest prime \(P\) was kept, while \(d_i>0\) means that we moved down by \(d_i\) positions in the prime list. The score loss caused by one such move is
$$\ell(d)=P-p_{k-1-d},\qquad \ell(0)=0.$$
Hence the total score becomes
$$S=\sum_{i=1}^{n} p_{a_i}=nP-\sum_{i=1}^{n}\ell(d_i).$$
Maximizing \(S\) is therefore equivalent to minimizing the total loss \(\sum \ell(d_i)\).
Since \(a_i=(k-1)-d_i\), we have
$$\sum_{i=1}^{n} a_i=n(k-1)-\sum_{i=1}^{n} d_i.$$
The congruence condition becomes
$$n(k-1)-\sum_{i=1}^{n} d_i\equiv 0 \pmod{k}.$$
Using \(k-1\equiv -1\pmod{k}\), this simplifies to
$$\sum_{i=1}^{n} d_i\equiv -n \pmod{k}.$$
Define the target residue
$$R\equiv -n \pmod{k},\qquad R=(k-(n\bmod k))\bmod k.$$
The original problem is now: choose deficits \(d_i\in\{0,\dots,k-1\}\) whose sum is congruent to \(R\) modulo \(k\), while making the total loss as small as possible.
The value \(d=0\) neither changes the residue class nor adds any loss. Such choices are useful only for padding the number of selected terms up to exactly \(n\). The real optimization is therefore to find the cheapest collection of nonzero deficits whose sum is congruent to \(R\) modulo \(k\).
At this point only the current residue matters, not the order in which the nonzero deficits were chosen. That observation leads directly to a shortest-path model.
Create a directed graph with vertices \(0,1,\dots,k-1\), where each vertex represents the current residue of the accumulated deficit sum modulo \(k\).
For every nonzero deficit \(d\in\{1,\dots,k-1\}\), add the transition
$$u\longrightarrow (u+d)\bmod k$$
with edge weight \(\ell(d)\).
If \(D(r)\) denotes the minimum path cost from residue \(0\) to residue \(r\), then \(D(r)\) is exactly the minimum total loss needed to achieve residue \(r\). Therefore
$$\boxed{S_{\max}=nP-D(R).}$$
Every edge corresponds to one nonzero deficit, so a path with \(t\) edges represents \(t\) genuine downgrades from the largest prime. Because every loss \(\ell(d)\) with \(d>0\) is positive, an optimal path never needs to repeat a vertex. If a residue appeared twice, the intermediate segment would be a positive-cost cycle, and deleting that cycle would keep the same final residue while lowering the total loss.
Thus a minimum-cost path can be taken to be simple, so it uses at most \(k-1\) edges. In the solved instance we have \(n\ge k-1\), so after finding the optimal path we can add enough zero deficits to reach exactly \(n\) chosen terms. Those extra terms do not change either the residue or the score. This proves that the residue shortest-path solution is exact for the original problem.
The first five primes are \(2,3,5,7,11\), so \(P=11\). The nonzero deficits have losses
$$\ell(1)=11-7=4,\quad \ell(2)=11-5=6,\quad \ell(3)=11-3=8,\quad \ell(4)=11-2=9.$$
The target residue is
$$R=(5-(8\bmod 5))\bmod 5=2.$$
One way to reach residue \(2\) is to take a single deficit \(d=2\), giving total loss \(6\). Another way is \(d=1+d=1\), but that costs \(4+4=8\), which is worse. So the minimum loss is \(D(2)=6\).
Hence
$$S_{\max}=8\cdot 11-6=82.$$
An optimal selection is to take the prime \(11\) seven times and the prime \(5\) once. The index sum is \(7\cdot 4+2=30\), and indeed \(30\equiv 0\pmod{5}\).
The implementations first generate enough primes with a sieve. They begin from a standard prime-number-theorem estimate for the search bound and enlarge that bound if it does not yet contain enough primes. This provides the first \(k\) primes used in the score, and also the next prime needed by the final input choice for \(n\).
They then compute the largest available prime \(P\), build the loss table \(\ell(d)\) for \(1\le d\le k-1\), and evaluate the target residue \(R=(-n)\bmod k\).
After that, the implementation runs Dijkstra's algorithm on the implicit residue graph. The distance array stores the best loss known so far for each residue. Whenever a residue is finalized, all \(k-1\) nonzero deficit transitions are relaxed.
Once the minimum loss \(D(R)\) is known, the result is returned as \(nP-D(R)\). One implementation also compares this fast method with a small exact dynamic program on tiny test cases, but the final computation uses only the shortest-path formulation.
The residue graph has \(k\) vertices and \(k(k-1)\) directed edges, generated implicitly. Dijkstra on this dense graph costs
$$O(k^2\log k)$$
time with a binary heap.
The sieve stage uses an upper bound \(B\) of order \(k(\log k+\log\log k)\), so prime generation costs \(O(B\log\log B)\) time and \(O(B)\) memory. For the actual parameters, the shortest-path stage is the dominant part.
The permanent arrays for the primes, losses, and finalized distances are \(O(k)\). With a standard heap implementation that pushes a fresh candidate whenever a better distance is found, the heap itself can grow to \(O(k^2)\) entries in the worst case.
Seien \(p_0=2,p_1=3,\dots,p_{k-1}\) die ersten \(k\) Primzahlen. Gewählt werden \(n\) Indizes \(a_1,\dots,a_n\in\{0,\dots,k-1\}\), und der Score ist
$$S=\sum_{i=1}^{n} p_{a_i}.$$
Zulässig sind genau die Auswahlen mit
$$\sum_{i=1}^{n} a_i\equiv 0 \pmod{k}.$$
Ohne diese Kongruenz wäre es optimal, immer die größte verfügbare Primzahl \(p_{k-1}\) zu nehmen. Der Kern der Aufgabe ist also, mit möglichst kleinem Punktverlust die richtige Restklasse für die Indexsumme zu erreichen.
Die C++-, Python- und Java-Implementierungen verwandeln die Maximierungsaufgabe in ein Minimalproblem auf den Restklassen modulo \(k\).
Setze
$$P=p_{k-1}.$$
Wenn jede Auswahl einfach \(P\) wäre, ergäbe sich der Score
$$nP.$$
Jede zulässige Lösung entsteht daraus, indem einige dieser größten Primzahlen durch kleinere Primzahlen ersetzt werden.
Für jeden gewählten Index definieren wir das Defizit
$$d_i=(k-1)-a_i,\qquad 0\le d_i\le k-1.$$
Der Fall \(d_i=0\) bedeutet, dass die größte Primzahl \(P\) beibehalten wird. Für \(d_i>0\) geht man um \(d_i\) Positionen in der Primzahlliste nach unten. Der dadurch verursachte Verlust ist
$$\ell(d)=P-p_{k-1-d},\qquad \ell(0)=0.$$
Damit wird der Gesamtscore zu
$$S=\sum_{i=1}^{n} p_{a_i}=nP-\sum_{i=1}^{n}\ell(d_i).$$
Den Score zu maximieren ist also dasselbe wie den Gesamtverlust \(\sum \ell(d_i)\) zu minimieren.
Aus \(a_i=(k-1)-d_i\) folgt
$$\sum_{i=1}^{n} a_i=n(k-1)-\sum_{i=1}^{n} d_i.$$
Die Bedingung wird zu
$$n(k-1)-\sum_{i=1}^{n} d_i\equiv 0 \pmod{k}.$$
Weil \(k-1\equiv -1\pmod{k}\), vereinfacht sich das zu
$$\sum_{i=1}^{n} d_i\equiv -n \pmod{k}.$$
Schreibe die Zielrestklasse als
$$R\equiv -n \pmod{k},\qquad R=(k-(n\bmod k))\bmod k.$$
Damit lautet das Problem nun: Wähle Defizite \(d_i\in\{0,\dots,k-1\}\), deren Summe kongruent zu \(R\) modulo \(k\) ist, und minimiere dabei den Gesamtverlust.
Der Wert \(d=0\) ändert weder die Restklasse noch den Scoreverlust. Solche Terme dienen nur dazu, die Anzahl der gewählten Elemente auf genau \(n\) aufzufüllen. Die eigentliche Optimierung besteht deshalb darin, die billigste Menge nichtnulliger Defizite zu finden, deren Summe die Restklasse \(R\) erzeugt.
Ab hier zählt nur noch die aktuelle Restklasse, nicht mehr die Reihenfolge der einzelnen Defizite. Genau daraus entsteht das Kürzeste-Wege-Modell.
Wir betrachten einen gerichteten Graphen mit den Knoten \(0,1,\dots,k-1\). Jeder Knoten steht für die aktuelle Restklasse der bisher aufsummierten Defizite modulo \(k\).
Für jedes nichtnullige Defizit \(d\in\{1,\dots,k-1\}\) gibt es den Übergang
$$u\longrightarrow (u+d)\bmod k$$
mit Kantenkosten \(\ell(d)\).
Bezeichnet \(D(r)\) die minimalen Kosten eines Pfades von \(0\) nach \(r\), dann ist \(D(r)\) genau der minimale Gesamtverlust, um die Restklasse \(r\) zu erreichen. Also gilt
$$\boxed{S_{\max}=nP-D(R).}$$
Jede Kante entspricht genau einem nichtnulligen Defizit, also einer echten Herabstufung von der größten Primzahl. Weil jeder Verlust \(\ell(d)\) für \(d>0\) positiv ist, braucht ein optimaler Pfad keinen wiederholten Knoten. Taucht dieselbe Restklasse zweimal auf, dann bildet das Zwischenstück einen positiven Zyklus. Entfernt man ihn, bleibt die Endrestklasse gleich, aber die Kosten sinken.
Ein minimaler Pfad kann daher einfach gewählt werden und besitzt höchstens \(k-1\) Kanten. In der berechneten Instanz gilt \(n\ge k-1\), also lässt sich der optimale Pfad auf genau \(n\) Auswahlen verlängern, indem man zusätzliche Defizite \(0\) anhängt. Diese verändern weder Restklasse noch Score. Damit ist gezeigt, dass der Restklassen-Pfad exakt dieselbe Aufgabe löst wie die ursprüngliche Auswahl von \(n\) Termen.
Die ersten fünf Primzahlen sind \(2,3,5,7,11\), also \(P=11\). Die nichtnulligen Defizite haben die Verluste
$$\ell(1)=11-7=4,\quad \ell(2)=11-5=6,\quad \ell(3)=11-3=8,\quad \ell(4)=11-2=9.$$
Die Zielrestklasse ist
$$R=(5-(8\bmod 5))\bmod 5=2.$$
Um Rest \(2\) zu erreichen, kann man einmal \(d=2\) nehmen; das kostet \(6\). Alternativ ginge \(d=1+d=1\), aber das kostet \(4+4=8\) und ist damit schlechter. Also ist der Minimalverlust \(D(2)=6\).
Folglich
$$S_{\max}=8\cdot 11-6=82.$$
Eine optimale Auswahl ist siebenmal die Primzahl \(11\) und einmal die Primzahl \(5\). Die Indizes summieren sich zu \(7\cdot 4+2=30\), und tatsächlich gilt \(30\equiv 0\pmod{5}\).
Die Implementierungen erzeugen zunächst genügend Primzahlen mit einem Sieb. Als Startwert für die Obergrenze dient eine übliche Abschätzung aus dem Primzahlsatz; falls diese noch nicht reicht, wird die Grenze vergrößert. So erhält man die ersten \(k\) Primzahlen für den Score sowie die nächste Primzahl, die in der finalen Eingabe als \(n\) gebraucht wird.
Danach werden die größte verfügbare Primzahl \(P\), die Verlusttabelle \(\ell(d)\) für \(1\le d\le k-1\) und die Zielrestklasse \(R=(-n)\bmod k\) berechnet.
Anschließend läuft Dijkstra auf dem impliziten Restklassen-Graphen. Das Distanzarray speichert für jede Restklasse den bisher besten bekannten Verlust. Immer wenn eine Restklasse mit endgültig minimalen Kosten entnommen wird, werden alle \(k-1\) nichtnulligen Übergänge relaxiert.
Sobald der minimale Verlust \(D(R)\) feststeht, lautet das Ergebnis \(nP-D(R)\). Eine Implementierung vergleicht diese schnelle Methode für sehr kleine Testfälle zusätzlich mit einem exakten dynamischen Programm, aber die eigentliche Berechnung verwendet nur das Kürzeste-Wege-Modell.
Der Restklassen-Graph besitzt \(k\) Knoten und \(k(k-1)\) gerichtete Kanten, die implizit erzeugt werden. Dijkstra auf diesem dichten Graphen benötigt
$$O(k^2\log k)$$
Zeit bei Verwendung eines Binär-Heaps.
Das Sieb arbeitet bis zu einer Schranke \(B\) von Größenordnung \(k(\log k+\log\log k)\), daher kostet die Primzahlerzeugung \(O(B\log\log B)\) Zeit und \(O(B)\) Speicher. Für die reale Instanz dominiert der Kürzeste-Wege-Teil.
Die dauerhaften Arrays für Primzahlen, Verluste und finale Distanzen benötigen \(O(k)\) Speicher. Bei einer Standard-Heap-Variante von Dijkstra, die bei jeder Verbesserung einen neuen Kandidaten einfügt, kann der Heap selbst im schlechtesten Fall bis zu \(O(k^2)\) Einträge enthalten.
\(p_0=2,p_1=3,\dots,p_{k-1}\) ilk \(k\) asal olsun. \(a_1,\dots,a_n\in\{0,\dots,k-1\}\) indeksleri seçiliyor ve skor
$$S=\sum_{i=1}^{n} p_{a_i}$$
olarak tanımlanıyor. Geçerli seçimlerin sağlaması gereken koşul ise
$$\sum_{i=1}^{n} a_i\equiv 0 \pmod{k}.$$
Bu mod koşulu olmasaydı her adımda en büyük asal \(p_{k-1}\) seçilirdi. O halde esas mesele, indeks toplamını doğru kalıntı sınıfına getirmek için gereken en küçük puan kaybını bulmaktır.
C++, Python ve Java uygulamalarının ortak fikri, bu maksimizasyon problemini mod \(k\) kalıntıları üzerinde bir minimum kayıp problemine dönüştürmektir.
Şunu yazalım:
$$P=p_{k-1}.$$
Eğer her seçim doğrudan \(P\) olabilseydi toplam skor
$$nP$$
olurdu. Her geçerli çözüm, bu ideal tablodan bazı seçimleri daha küçük asal sayılarla değiştirerek elde edilir.
Her seçilen indeks için
$$d_i=(k-1)-a_i,\qquad 0\le d_i\le k-1$$
tanımını yapalım. \(d_i=0\) ise en büyük asal \(P\) korunmuştur. \(d_i>0\) ise asal listesinde \(d_i\) basamak aşağı inilmiştir. Bu inişin skorda oluşturduğu kayıp
$$\ell(d)=P-p_{k-1-d},\qquad \ell(0)=0$$
olur. Böylece toplam skor
$$S=\sum_{i=1}^{n} p_{a_i}=nP-\sum_{i=1}^{n}\ell(d_i)$$
şeklini alır. Yani \(S\)'yi maksimize etmek, toplam kaybı minimize etmekle aynıdır.
\(a_i=(k-1)-d_i\) olduğundan
$$\sum_{i=1}^{n} a_i=n(k-1)-\sum_{i=1}^{n} d_i.$$
Verilen koşul
$$n(k-1)-\sum_{i=1}^{n} d_i\equiv 0 \pmod{k}$$
haline gelir. \(k-1\equiv -1\pmod{k}\) olduğu için bu ifade
$$\sum_{i=1}^{n} d_i\equiv -n \pmod{k}$$
olarak sadeleşir. Hedef kalıntıyı
$$R\equiv -n \pmod{k},\qquad R=(k-(n\bmod k))\bmod k$$
şeklinde tanımlarsak artık problem şudur: toplamı mod \(k\)'de \(R\)'ye denk olan açıklar seç ve toplam kaybı en aza indir.
\(d=0\) ne kalıntıyı değiştirir ne de kayıp ekler. Bu tür seçimler yalnızca toplam eleman sayısını tam olarak \(n\)'e tamamlamak için gerekir. Dolayısıyla gerçek optimizasyon, toplamı \(R\) kalıntısını veren sıfırdan farklı açıkların en ucuz birleşimini bulmaktır.
Bu noktada sıranın önemi kalmaz; önemli olan yalnızca elde edilen güncel kalıntıdır. Böylece problem doğal olarak bir en kısa yol modeline dönüşür.
\(0,1,\dots,k-1\) düğümlerinden oluşan yönlü bir grafik düşünelim. Her düğüm, o ana kadar toplanan açıkların mod \(k\)'deki kalıntısını temsil eder.
Her sıfırdan farklı açık \(d\in\{1,\dots,k-1\}\) için
$$u\longrightarrow (u+d)\bmod k$$
geçişini ve bu geçiş için \(\ell(d)\) ağırlığını ekleyelim.
\(D(r)\), \(0\) kalıntısından \(r\) kalıntısına en küçük yol maliyeti olsun. O zaman \(D(r)\), kalıntı \(r\)'ye ulaşmak için gereken en küçük toplam kayıptır. Bu yüzden
$$\boxed{S_{\max}=nP-D(R).}$$
Her kenar bir sıfırdan farklı açığa, yani en büyük asaldan gerçek bir geri adıma karşılık gelir. \(d>0\) için her \(\ell(d)\) pozitif olduğundan, optimal bir yol aynı düğümü tekrar ziyaret etmek zorunda değildir. Aynı kalıntı iki kez görülse, aradaki parça pozitif maliyetli bir çevrim olur. Bu çevrimi çıkarmak son kalıntıyı korur ama toplam kaybı azaltır.
Demek ki en iyi yol basit seçilebilir ve en fazla \(k-1\) kenar içerir. Çözülen örnekte \(n\ge k-1\) olduğu için, bulunan optimal yol yeterince çok sayıda \(d=0\) eklenerek tam \(n\) seçime tamamlanabilir. Bu ekler ne kalıntıyı ne de skoru değiştirir. Böylece kalıntı grafındaki en kısa yolun, özgün problemle tam olarak aynı cevabı verdiği kanıtlanmış olur.
İlk beş asal \(2,3,5,7,11\) olduğundan \(P=11\)'dir. Sıfırdan farklı açıkların kayıpları
$$\ell(1)=11-7=4,\quad \ell(2)=11-5=6,\quad \ell(3)=11-3=8,\quad \ell(4)=11-2=9$$
olur. Hedef kalıntı
$$R=(5-(8\bmod 5))\bmod 5=2$$
şeklindedir. Kalıntı \(2\)'ye ulaşmanın bir yolu tek bir \(d=2\) seçmektir; bunun kaybı \(6\)'dır. Bir başka yol \(d=1+d=1\) almaktır, fakat bunun maliyeti \(4+4=8\) olur. Dolayısıyla en küçük kayıp \(D(2)=6\)'dır.
Böylece
$$S_{\max}=8\cdot 11-6=82$$
elde edilir. En iyi seçimlerden biri, \(11\) asalını yedi kez ve \(5\) asalını bir kez almaktır. İndeks toplamı \(7\cdot 4+2=30\) olur ve gerçekten \(30\equiv 0\pmod{5}\).
Uygulamalar önce yeterli sayıda asal üretir. Bunun için asal sayılar teoreminden gelen standart bir üst sınır tahminiyle başlayan bir elek kurulur; yetmezse sınır büyütülür. Böylece skorda kullanılacak ilk \(k\) asal ve son girişte \(n\) için gereken bir sonraki asal elde edilir.
Daha sonra en büyük mevcut asal \(P\), \(1\le d\le k-1\) için kayıp tablosu \(\ell(d)\) ve hedef kalıntı \(R=(-n)\bmod k\) hesaplanır.
Bunun ardından örtük kalıntı grafı üzerinde Dijkstra algoritması çalıştırılır. Uzaklık dizisi, her kalıntı için o ana dek bulunan en iyi kaybı tutar. Bir kalıntının en küçük maliyeti kesinleştiğinde, tüm \(k-1\) adet sıfırdan farklı geçiş gevşetilir.
Son olarak minimum kayıp \(D(R)\) bulunduğunda sonuç \(nP-D(R)\) olarak döndürülür. Uygulamalardan biri küçük örneklerde bu hızlı yöntemi tam bir dinamik programla da karşılaştırır, fakat gerçek hesaplama tamamen en kısa yol formülasyonuna dayanır.
Kalıntı grafı \(k\) düğüm ve \(k(k-1)\) yönlü kenar içerir; kenarlar gerektiğinde üretilir. Bu yoğun grafik üzerinde Dijkstra'nın maliyeti
$$O(k^2\log k)$$
zamandır.
Elek aşaması, büyüklüğü \(k(\log k+\log\log k)\) mertebesindeki bir \(B\) üst sınırına kadar çalışır; dolayısıyla asal üretimi \(O(B\log\log B)\) zaman ve \(O(B)\) bellek gerektirir. Gerçek parametrelerde baskın maliyet en kısa yol aşamasıdır.
Asallar, kayıplar ve son uzaklıklar için gereken kalıcı diziler \(O(k)\) bellektir. Her iyileşmede yığına yeni aday ekleyen standart Dijkstra uygulamasında, yığın en kötü durumda \(O(k^2)\) girişe kadar büyüyebilir.
Sean \(p_0=2,p_1=3,\dots,p_{k-1}\) los primeros \(k\) primos. Se eligen \(n\) índices \(a_1,\dots,a_n\in\{0,\dots,k-1\}\) y la puntuación es
$$S=\sum_{i=1}^{n} p_{a_i}.$$
La restricción de validez es
$$\sum_{i=1}^{n} a_i\equiv 0 \pmod{k}.$$
Si se ignorara esa congruencia, siempre convendría escoger el primo más grande disponible, \(p_{k-1}\). Por tanto, el problema real consiste en medir la menor penalización necesaria para corregir la clase residual de la suma de índices sin perder más puntuación de la imprescindible.
Las implementaciones en C++, Python y Java convierten la maximización con restricción en un problema de pérdida mínima sobre residuos módulo \(k\).
Escribimos
$$P=p_{k-1}.$$
Si todas las elecciones pudieran ser \(P\), la puntuación sería
$$nP.$$
Cualquier solución válida solo puede diferir de ese ideal porque algunas elecciones deben reemplazar \(P\) por primos más pequeños.
Para cada índice elegido definimos
$$d_i=(k-1)-a_i,\qquad 0\le d_i\le k-1.$$
Entonces \(d_i=0\) significa “mantener el primo máximo”, mientras que \(d_i>0\) significa bajar \(d_i\) posiciones en la lista de primos. La pérdida producida por ese descenso es
$$\ell(d)=P-p_{k-1-d},\qquad \ell(0)=0.$$
La puntuación total pasa a ser
$$S=\sum_{i=1}^{n} p_{a_i}=nP-\sum_{i=1}^{n}\ell(d_i).$$
Así, maximizar \(S\) equivale a minimizar la pérdida total \(\sum \ell(d_i)\).
Como \(a_i=(k-1)-d_i\), se tiene
$$\sum_{i=1}^{n} a_i=n(k-1)-\sum_{i=1}^{n} d_i.$$
La restricción se transforma en
$$n(k-1)-\sum_{i=1}^{n} d_i\equiv 0 \pmod{k}.$$
Puesto que \(k-1\equiv -1\pmod{k}\), esto se simplifica a
$$\sum_{i=1}^{n} d_i\equiv -n \pmod{k}.$$
Definimos el residuo objetivo por
$$R\equiv -n \pmod{k},\qquad R=(k-(n\bmod k))\bmod k.$$
El problema original queda reducido a elegir déficits \(d_i\in\{0,\dots,k-1\}\) cuya suma sea congruente con \(R\) módulo \(k\), minimizando al mismo tiempo la pérdida total.
El valor \(d=0\) no cambia el residuo ni añade pérdida. Solo sirve para completar el número total de términos hasta exactamente \(n\). Por eso la parte combinatoria importante es hallar la colección más barata de déficits no nulos cuya suma produzca el residuo \(R\).
En ese punto solo importa el residuo actual, no el orden de los déficits. Esa observación lleva de forma natural a un problema de camino mínimo.
Se considera un grafo dirigido con vértices \(0,1,\dots,k-1\). Cada vértice representa el residuo actual de la suma acumulada de déficits módulo \(k\).
Para cada déficit no nulo \(d\in\{1,\dots,k-1\}\), añadimos la transición
$$u\longrightarrow (u+d)\bmod k$$
con peso \(\ell(d)\).
Si \(D(r)\) es el coste mínimo de un camino desde el residuo \(0\) hasta el residuo \(r\), entonces \(D(r)\) es exactamente la menor pérdida total necesaria para alcanzar \(r\). Por tanto
$$\boxed{S_{\max}=nP-D(R).}$$
Cada arista representa un déficit no nulo, es decir, una sustitución real del primo máximo por otro menor. Como toda pérdida \(\ell(d)\) con \(d>0\) es positiva, un camino óptimo no necesita repetir vértices. Si un residuo apareciera dos veces, el tramo intermedio sería un ciclo de coste positivo. Al eliminarlo se conserva el mismo residuo final, pero con menor pérdida.
Así, un camino mínimo puede tomarse simple y por ello tiene a lo sumo \(k-1\) aristas. En la instancia resuelta se cumple \(n\ge k-1\), de modo que el camino óptimo puede completarse hasta tener exactamente \(n\) elecciones añadiendo déficits nulos. Esos términos extra no alteran ni el residuo ni la puntuación. Con ello queda demostrado que el modelo de camino mínimo da la respuesta exacta del problema original.
Los primeros cinco primos son \(2,3,5,7,11\), luego \(P=11\). Las pérdidas asociadas a los déficits no nulos son
$$\ell(1)=11-7=4,\quad \ell(2)=11-5=6,\quad \ell(3)=11-3=8,\quad \ell(4)=11-2=9.$$
El residuo objetivo es
$$R=(5-(8\bmod 5))\bmod 5=2.$$
Una forma de llegar al residuo \(2\) es tomar un único déficit \(d=2\), con pérdida total \(6\). Otra posibilidad es \(d=1+d=1\), pero cuesta \(4+4=8\), así que es peor. Por lo tanto el mínimo es \(D(2)=6\).
En consecuencia
$$S_{\max}=8\cdot 11-6=82.$$
Una selección óptima consiste en escoger el primo \(11\) siete veces y el primo \(5\) una vez. La suma de índices es \(7\cdot 4+2=30\), y en efecto \(30\equiv 0\pmod{5}\).
Las implementaciones primero generan suficientes primos mediante una criba. Comienzan con una cota superior estándar basada en el teorema de los números primos y amplían esa cota si todavía no aparecen suficientes primos. Así obtienen los primeros \(k\) primos usados en la puntuación y también el siguiente primo necesario para la elección final de \(n\).
Después calculan el primo máximo disponible \(P\), construyen la tabla de pérdidas \(\ell(d)\) para \(1\le d\le k-1\) y evalúan el residuo objetivo \(R=(-n)\bmod k\).
A continuación la implementación ejecuta el algoritmo de Dijkstra sobre el grafo implícito de residuos. El arreglo de distancias guarda la mejor pérdida conocida para cada residuo. Cada vez que un residuo queda fijado con coste mínimo definitivo, se relajan las \(k-1\) transiciones no nulas.
Una vez conocido el valor mínimo \(D(R)\), la respuesta se devuelve como \(nP-D(R)\). Una de las implementaciones compara este método rápido con un pequeño programa dinámico exacto en casos diminutos, pero el cálculo final usa únicamente la formulación de camino mínimo.
El grafo de residuos tiene \(k\) vértices y \(k(k-1)\) aristas dirigidas, generadas de forma implícita. Ejecutar Dijkstra en este grafo denso cuesta
$$O(k^2\log k)$$
tiempo con un heap binario.
La fase de la criba utiliza una cota \(B\) del orden de \(k(\log k+\log\log k)\), de modo que la generación de primos cuesta \(O(B\log\log B)\) tiempo y \(O(B)\) memoria. Para los parámetros reales domina claramente la etapa del camino mínimo.
Los arreglos permanentes para primos, pérdidas y distancias finales ocupan \(O(k)\) memoria. Con la versión habitual de Dijkstra que inserta un nuevo candidato cada vez que mejora una distancia, el heap puede crecer hasta \(O(k^2)\) entradas en el peor caso.
设 \(p_0=2,p_1=3,\dots,p_{k-1}\) 是前 \(k\) 个素数。我们要选择 \(n\) 个下标 \(a_1,\dots,a_n\in\{0,\dots,k-1\}\)，并把得分定义为
$$S=\sum_{i=1}^{n} p_{a_i}.$$
可行解必须满足
$$\sum_{i=1}^{n} a_i\equiv 0 \pmod{k}.$$
如果没有这个同余限制，那么显然每一项都取最大的素数 \(p_{k-1}\) 才最优。因此真正的问题不是“怎样挑最大”，而是“为了把下标和修正到正确的模 \(k\) 余数，最少要牺牲多少分数”。
C++、Python 和 Java 实现都把这个带同余约束的最大化问题，转化成模 \(k\) 余数图上的最小损失问题。
记
$$P=p_{k-1}.$$
如果每一项都能直接取到 \(P\)，那么总分就是
$$nP.$$
任何合法方案都只是在这个理想上做少量下调，也就是把若干个最大的素数换成列表中更小的素数。
对每个选中的下标定义
$$d_i=(k-1)-a_i,\qquad 0\le d_i\le k-1.$$
这里 \(d_i=0\) 表示仍然选最大素数 \(P\)，而 \(d_i>0\) 表示在素数表中向前退了 \(d_i\) 个位置。一次这样的退步造成的分数损失定义为
$$\ell(d)=P-p_{k-1-d},\qquad \ell(0)=0.$$
于是总分可以重写为
$$S=\sum_{i=1}^{n} p_{a_i}=nP-\sum_{i=1}^{n}\ell(d_i).$$
所以最大化 \(S\)，等价于最小化总损失 \(\sum \ell(d_i)\)。这一步把“尽量大”变成了“尽量少损失”，结构上清晰得多。
因为 \(a_i=(k-1)-d_i\)，所以
$$\sum_{i=1}^{n} a_i=n(k-1)-\sum_{i=1}^{n} d_i.$$
原条件
$$\sum_{i=1}^{n} a_i\equiv 0 \pmod{k}$$
就变成
$$n(k-1)-\sum_{i=1}^{n} d_i\equiv 0 \pmod{k}.$$
再利用 \(k-1\equiv -1\pmod{k}\)，得到
$$\sum_{i=1}^{n} d_i\equiv -n \pmod{k}.$$
设目标余数为
$$R\equiv -n \pmod{k},\qquad R=(k-(n\bmod k))\bmod k.$$
这样一来，原题就变成了：在 \(d_i\in\{0,\dots,k-1\}\) 中选择若干项，使得它们的和模 \(k\) 等于 \(R\)，并且总损失最小。
\(d=0\) 有两个特殊性质：它不会改变当前余数，也不会增加任何损失。换句话说，零缺口只负责“补长度”，不参与真正的优化。因此我们真正要解决的是：怎样用若干个非零缺口，以最小代价凑出目标余数 \(R\)。
一旦写成这个样子，就会发现顺序已经不重要了。对后续状态真正有影响的只有“当前缺口和的余数”这一件事。于是问题自然落到一个余数状态图上。
构造一个有向图，顶点为 \(0,1,\dots,k-1\)。顶点 \(u\) 表示当前所有缺口之和对 \(k\) 取模后等于 \(u\)。
对每个非零缺口 \(d\in\{1,\dots,k-1\}\)，都加入一条转移
$$u\longrightarrow (u+d)\bmod k$$
边权就是对应的损失 \(\ell(d)\)。
记 \(D(r)\) 为从余数 \(0\) 走到余数 \(r\) 的最小路径代价，那么 \(D(r)\) 恰好就是把缺口和凑成余数 \(r\) 所需的最小总损失。因此最优得分满足
$$\boxed{S_{\max}=nP-D(R).}$$
这一步是整个方法的核心：原问题不再是指数级组合搜索，而是一个标准的带正权最短路问题。
图中的每一条边都对应一个非零缺口，也就是一次真正把最大素数换成较小素数的操作。如果某条最优路径中某个顶点出现了两次，那么中间那一段就是一个总余数为 \(0\) 的回路。由于所有非零缺口的损失都为正，这个回路的总代价也为正，把它删掉以后终点余数不变，但总损失更小，这与“最优”矛盾。
因此最小代价路径一定可以取为简单路径，于是边数最多只有 \(k-1\) 条。在实际求解的参数下有 \(n\ge k-1\)，所以只要先找到这条最优简单路径，再补上足够多的零缺口，就能把总选择次数补足到恰好 \(n\) 次。补上的零缺口既不改变余数，也不增加损失，所以最终得分完全不变。由此可知，余数图上的最短路答案与原题答案严格一致。
前五个素数是 \(2,3,5,7,11\)，所以 \(P=11\)。各个非零缺口对应的损失为
$$\ell(1)=11-7=4,\quad \ell(2)=11-5=6,\quad \ell(3)=11-3=8,\quad \ell(4)=11-2=9.$$
目标余数是
$$R=(5-(8\bmod 5))\bmod 5=2.$$
要得到余数 \(2\)，一种办法是直接取一个缺口 \(d=2\)，总代价为 \(6\)。另一种办法是取 \(d=1+d=1\)，但总代价变成 \(4+4=8\)，更差。因此最小损失就是 \(D(2)=6\)。
于是
$$S_{\max}=8\cdot 11-6=82.$$
一个最优方案是选 \(11\) 七次、选 \(5\) 一次。对应下标和为 \(7\cdot 4+2=30\)，确实满足 \(30\equiv 0\pmod{5}\)。这个例子完整展示了“最大基线减去最小修正成本”的思路。
实现的第一步是用筛法生成足够多的素数。初始筛范围来自一个常见的素数定理上界估计；如果该范围内的素数数量还不够，就把上界继续放大。这样既能得到得分计算需要的前 \(k\) 个素数，也能得到最终输入中用于 \(n\) 的下一个素数。
接着，程序取出最大的可用素数 \(P\)，预计算 \(1\le d\le k-1\) 的损失表 \(\ell(d)\)，并求出目标余数 \(R=(-n)\bmod k\)。
随后，程序在隐式余数图上运行 Dijkstra 算法。距离数组保存“到达每个余数时目前已知的最小损失”。当某个余数以最终最优代价弹出后，程序就尝试用全部 \(k-1\) 个非零缺口去松弛后继状态。
当 \(D(R)\) 求出以后，答案直接写成 \(nP-D(R)\)。其中一个实现还会在很小的参数上，把快速算法与一个精确动态规划做交叉检查，但正式计算依赖的仍然只是这个余数最短路模型。
余数图共有 \(k\) 个顶点和 \(k(k-1)\) 条有向边，边是按需隐式生成的。在这样的稠密图上运行 Dijkstra，时间复杂度为
$$O(k^2\log k).$$
筛法阶段使用的上界 \(B\) 大约是 \(k(\log k+\log\log k)\) 的量级，所以生成素数的代价是 \(O(B\log\log B)\) 时间和 \(O(B)\) 空间。对实际参数来说，主导开销仍然是最短路阶段。
用于保存素数、损失和最终距离的常驻数组是 \(O(k)\) 空间。如果采用标准的堆式 Dijkstra 写法，也就是每次发现更优距离就向堆中再压入一个候选状态，那么堆本身在最坏情况下可能增长到 \(O(k^2)\) 个条目。
Пусть \(p_0=2,p_1=3,\dots,p_{k-1}\) — первые \(k\) простых чисел. Нужно выбрать \(n\) индексов \(a_1,\dots,a_n\in\{0,\dots,k-1\}\) и максимизировать сумму
$$S=\sum_{i=1}^{n} p_{a_i}.$$
Допустимы только те выборы, для которых
$$\sum_{i=1}^{n} a_i\equiv 0 \pmod{k}.$$
Без этого сравнения по модулю ответ был бы очевиден: всегда брать наибольшее доступное простое \(p_{k-1}\). Значит, главное — понять, какой минимальный штраф по сумме нужно заплатить, чтобы исправить остаток суммы индексов.
Во всех трёх реализациях задача максимизации с ограничением переписывается как задача о минимальной потере на остатках по модулю \(k\).
Обозначим
$$P=p_{k-1}.$$
Если бы каждое слагаемое можно было брать равным \(P\), итоговый счёт был бы равен
$$nP.$$
Любое допустимое решение отличается от этого идеала только тем, что некоторые такие максимальные выборы приходится заменить меньшими простыми числами.
Для каждого выбранного индекса введём дефицит
$$d_i=(k-1)-a_i,\qquad 0\le d_i\le k-1.$$
Значение \(d_i=0\) означает, что мы оставили максимальное простое \(P\). При \(d_i>0\) мы сместились на \(d_i\) позиций вниз по списку простых. Потеря очков от такого смещения равна
$$\ell(d)=P-p_{k-1-d},\qquad \ell(0)=0.$$
Тогда общая сумма переписывается так:
$$S=\sum_{i=1}^{n} p_{a_i}=nP-\sum_{i=1}^{n}\ell(d_i).$$
Следовательно, максимизация \(S\) эквивалентна минимизации полной потери \(\sum \ell(d_i)\).
Так как \(a_i=(k-1)-d_i\), имеем
$$\sum_{i=1}^{n} a_i=n(k-1)-\sum_{i=1}^{n} d_i.$$
Ограничение превращается в
$$n(k-1)-\sum_{i=1}^{n} d_i\equiv 0 \pmod{k}.$$
Из \(k-1\equiv -1\pmod{k}\) получаем
$$\sum_{i=1}^{n} d_i\equiv -n \pmod{k}.$$
Введём целевой остаток
$$R\equiv -n \pmod{k},\qquad R=(k-(n\bmod k))\bmod k.$$
После этого задача формулируется так: выбрать дефициты \(d_i\in\{0,\dots,k-1\}\), сумма которых сравнима с \(R\) по модулю \(k\), и при этом сделать суммарную потерю минимальной.
Значение \(d=0\) не меняет остаток и не добавляет потери. Такие шаги нужны только затем, чтобы общее число выбранных элементов оказалось ровно \(n\). Поэтому реальная оптимизация заключается в поиске самой дешёвой комбинации ненулевых дефицитов, дающей остаток \(R\).
На этом этапе становится ясно, что порядок уже несущественен: для будущего важен только текущий остаток. Именно это и приводит к модели кратчайшего пути.
Рассмотрим ориентированный граф с вершинами \(0,1,\dots,k-1\). Вершина \(u\) означает, что сумма уже выбранных дефицитов даёт остаток \(u\) по модулю \(k\).
Для каждого ненулевого дефицита \(d\in\{1,\dots,k-1\}\) добавим переход
$$u\longrightarrow (u+d)\bmod k$$
с весом \(\ell(d)\).
Если \(D(r)\) — минимальная стоимость пути из остатка \(0\) в остаток \(r\), то это в точности минимальная суммарная потеря, необходимая для достижения остатка \(r\). Поэтому
$$\boxed{S_{\max}=nP-D(R).}$$
Каждое ребро соответствует одному ненулевому дефициту, то есть одной реальной замене максимального простого на меньшее. Поскольку для \(d>0\) все величины \(\ell(d)\) положительны, оптимальному пути не нужно повторять вершины. Если некоторый остаток встретился дважды, то промежуточный участок образует цикл положительной стоимости. Удаление такого цикла сохраняет конечный остаток, но уменьшает потерю.
Значит, минимальный путь можно взять простым, а у простого пути не больше \(k-1\) рёбер. В решаемой постановке выполняется \(n\ge k-1\), поэтому найденный оптимальный путь можно дополнить нулевыми дефицитами до ровно \(n\) выборов. Эти дополнительные шаги ничего не меняют ни в остатке, ни в сумме. Следовательно, кратчайший путь по графу остатков решает исходную задачу точно, а не приближённо.
Первые пять простых — это \(2,3,5,7,11\), так что \(P=11\). Потери для ненулевых дефицитов равны
$$\ell(1)=11-7=4,\quad \ell(2)=11-5=6,\quad \ell(3)=11-3=8,\quad \ell(4)=11-2=9.$$
Целевой остаток равен
$$R=(5-(8\bmod 5))\bmod 5=2.$$
Один способ получить остаток \(2\) — взять один дефицит \(d=2\), и тогда потеря равна \(6\). Другой способ — взять \(d=1+d=1\), но это стоит \(4+4=8\), что хуже. Значит, минимальная потеря равна \(D(2)=6\).
Отсюда
$$S_{\max}=8\cdot 11-6=82.$$
Один из оптимальных выборов: семь раз взять простое \(11\) и один раз простое \(5\). Сумма индексов тогда равна \(7\cdot 4+2=30\), и действительно \(30\equiv 0\pmod{5}\).
Сначала реализации генерируют достаточно много простых чисел с помощью решета. Начальная верхняя граница берётся из стандартной оценки, основанной на теореме о распределении простых чисел; если простых всё ещё мало, граница увеличивается. Так получаются первые \(k\) простых для самой задачи и следующее простое, используемое в финальном выборе параметра \(n\).
Затем вычисляются максимальное доступное простое \(P\), таблица потерь \(\ell(d)\) для \(1\le d\le k-1\) и целевой остаток \(R=(-n)\bmod k\).
После этого запускается алгоритм Дейкстры на неявном графе остатков. Массив расстояний хранит лучшую найденную потерю для каждого остатка. Когда очередной остаток извлекается с окончательной минимальной стоимостью, релаксируются все \(k-1\) ненулевых переходов.
Как только найдено значение \(D(R)\), ответ вычисляется как \(nP-D(R)\). В одной из реализаций быстрый метод дополнительно сверяется с точной динамикой на маленьких тестах, но для реального подсчёта используется только модель кратчайшего пути.
Граф остатков имеет \(k\) вершин и \(k(k-1)\) ориентированных рёбер, которые порождаются неявно. Алгоритм Дейкстры на таком плотном графе работает за
$$O(k^2\log k)$$
времени при использовании бинарной кучи.
Этап решета использует верхнюю границу \(B\) порядка \(k(\log k+\log\log k)\), поэтому генерация простых чисел требует \(O(B\log\log B)\) времени и \(O(B)\) памяти. Для реальных параметров главным остаётся именно этап кратчайшего пути.
Постоянные массивы для простых, потерь и окончательных расстояний занимают \(O(k)\) памяти. Если использовать обычную кучную реализацию Дейкстры, где при каждом улучшении расстояния в кучу добавляется новый кандидат, сама куча в худшем случае может вырасти до \(O(k^2)\) элементов.
لتكن \(p_0=2,p_1=3,\dots,p_{k-1}\) هي أول \(k\) أعداد أولية. نختار \(n\) فهارس \(a_1,\dots,a_n\in\{0,\dots,k-1\}\)، وتكون الدرجة
$$S=\sum_{i=1}^{n} p_{a_i}.$$
والقيد الذي يجب تحقيقه هو
$$\sum_{i=1}^{n} a_i\equiv 0 \pmod{k}.$$
لو لم يوجد هذا القيد لكان الحل البديهي هو اختيار أكبر أولي متاح \(p_{k-1}\) في كل مرة. لذلك فجوهر المسألة هو تحديد أقل خسارة ممكنة نحتاج إليها من أجل تصحيح باقي مجموع الفهارس مع الحفاظ على أكبر مجموع ممكن.
المنهج المشترك في تطبيقات C++ وPython وJava هو تحويل مسألة التعظيم المقيدة إلى مسألة تقليل خسارة على فئات البواقي modulo \(k\).
لنكتب
$$P=p_{k-1}.$$
إذا كان مسموحًا أن تكون كل اختيار مساويًا لـ \(P\)، فإن الدرجة تصبح
$$nP.$$
وأي حل قانوني لا يختلف عن هذا الوضع المثالي إلا لأن بعض هذه الاختيارات يجب أن تُستبدل بأعداد أولية أصغر.
لكل فهرس مختار نعرّف
$$d_i=(k-1)-a_i,\qquad 0\le d_i\le k-1.$$
إذا كان \(d_i=0\) فهذا يعني أننا أبقينا على أكبر أولي \(P\). وإذا كان \(d_i>0\) فهذا يعني أننا تراجعنا \(d_i\) مراتب داخل قائمة الأعداد الأولية. والخسارة الناتجة عن هذا التراجع هي
$$\ell(d)=P-p_{k-1-d},\qquad \ell(0)=0.$$
وعندها يمكن كتابة الدرجة الكلية بالشكل
$$S=\sum_{i=1}^{n} p_{a_i}=nP-\sum_{i=1}^{n}\ell(d_i).$$
إذن تعظيم \(S\) يكافئ تمامًا تصغير الخسارة الكلية \(\sum \ell(d_i)\).
بما أن \(a_i=(k-1)-d_i\)، فإن
$$\sum_{i=1}^{n} a_i=n(k-1)-\sum_{i=1}^{n} d_i.$$
ومن ثم يصبح القيد
$$n(k-1)-\sum_{i=1}^{n} d_i\equiv 0 \pmod{k}.$$
ولأن \(k-1\equiv -1\pmod{k}\)، نحصل على
$$\sum_{i=1}^{n} d_i\equiv -n \pmod{k}.$$
لنعرّف الباقي الهدف على أنه
$$R\equiv -n \pmod{k},\qquad R=(k-(n\bmod k))\bmod k.$$
وهكذا تصبح المسألة: اختر قيمًا \(d_i\in\{0,\dots,k-1\}\) بحيث يكون مجموعها مكافئًا لـ \(R\) modulo \(k\)، مع جعل الخسارة الكلية أصغر ما يمكن.
القيمة \(d=0\) لا تغيّر الباقي ولا تضيف أي خسارة. لذا فهي لا تقوم بدور حقيقي في التحسين نفسه، بل تُستخدم فقط لإكمال عدد الاختيارات حتى يصبح بالضبط \(n\). ومن ثم فإن الجزء الفعلي من المسألة هو: ما أرخص مجموعة من العجوزات غير الصفرية التي تحقق الباقي \(R\)؟
عند هذه النقطة لم يعد ترتيب هذه العجوزات مهمًا؛ المهم فقط هو الباقي الحالي. وهذا بالضبط ما يقود إلى نموذج أقصر مسار.
ننشئ رسمًا بيانيًا موجهًا رؤوسه هي \(0,1,\dots,k-1\). الرأس \(u\) يمثّل الباقي الحالي لمجموع العجوزات modulo \(k\).
ولكل عجز غير صفري \(d\in\{1,\dots,k-1\}\) نضيف الانتقال
$$u\longrightarrow (u+d)\bmod k$$
بوزن يساوي \(\ell(d)\).
إذا رمزنا إلى أقل كلفة للوصول من الباقي \(0\) إلى الباقي \(r\) بالرمز \(D(r)\)، فإن \(D(r)\) هو بالضبط أقل خسارة كلية مطلوبة لتحقيق ذلك الباقي. لذلك يكون الحل الأمثل
$$\boxed{S_{\max}=nP-D(R).}$$
كل ضلع في الرسم البياني يقابل عجزًا غير صفري، أي استبدالًا حقيقيًا للعدد الأولي الأكبر بعدد أولي أصغر. وبما أن كل خسارة \(\ell(d)\) عندما \(d>0\) موجبة، فإن أي مسار أمثل لا يحتاج إلى تكرار رأس. فإذا ظهر نفس الباقي مرتين، فإن المقطع الواقع بينهما يشكل دورة ذات كلفة موجبة. حذف تلك الدورة يحافظ على الباقي النهائي نفسه، لكنه يخفض الخسارة، وهذا يناقض المثالية.
إذن يمكن أخذ المسار الأدنى كلفة على أنه مسار بسيط، وبالتالي لا يتجاوز عدد أضلاعه \(k-1\). وفي الحالة التي تحسبها التطبيقات لدينا \(n\ge k-1\)، لذلك نستطيع بعد إيجاد المسار الأمثل أن نضيف ما يكفي من العجوزات الصفرية حتى يصبح عدد العناصر المختارة بالضبط \(n\). هذه الإضافات لا تغيّر الباقي ولا الدرجة، ومن ثم فإن حل أقصر مسار يطابق تمامًا الحل الأصلي للمسألة.
الأعداد الأولية الخمسة الأولى هي \(2,3,5,7,11\)، لذا \(P=11\). والخسائر المقابلة للعجوزات غير الصفرية هي
$$\ell(1)=11-7=4,\quad \ell(2)=11-5=6,\quad \ell(3)=11-3=8,\quad \ell(4)=11-2=9.$$
أما الباقي الهدف فهو
$$R=(5-(8\bmod 5))\bmod 5=2.$$
للوصول إلى الباقي \(2\) يمكن أخذ عجز واحد \(d=2\) فتكون الخسارة \(6\). وهناك خيار آخر هو \(d=1+d=1\)، لكن كلفته \(4+4=8\)، وهو أسوأ. إذن أقل خسارة هي \(D(2)=6\).
وبالتالي
$$S_{\max}=8\cdot 11-6=82.$$
ومن الاختيارات المثلى أن نأخذ العدد الأولي \(11\) سبع مرات والعدد الأولي \(5\) مرة واحدة. عندئذ يكون مجموع الفهارس \(7\cdot 4+2=30\)، فعلًا \(30\equiv 0\pmod{5}\).
تبدأ التطبيقات بتوليد عدد كاف من الأعداد الأولية باستخدام غربال. وتُختار في البداية قيمة عليا معيارية مستندة إلى نظرية الأعداد الأولية، ثم تُزاد هذه القيمة إذا لم تكن كافية للحصول على العدد المطلوب من الأوليات. بهذه الطريقة نحصل على أول \(k\) أوليات المستخدمة في حساب الدرجة، وكذلك على الأولي التالي اللازم في الاختيار النهائي لقيمة \(n\).
بعد ذلك تُحسب أكبر قيمة أولية متاحة \(P\)، ويُبنى جدول الخسائر \(\ell(d)\) للقيم \(1\le d\le k-1\)، ثم يُحسب الباقي الهدف \(R=(-n)\bmod k\).
بعدها تشغّل الخوارزمية Dijkstra على رسم البواقي الضمني. مصفوفة المسافات تحتفظ بأفضل خسارة معروفة حتى تلك اللحظة لكل باقٍ. وكلما ثُبّتت كلفة دنيا لرأس ما، تُجرى عملية Relax لكل الانتقالات غير الصفرية وعددها \(k-1\).
وعندما تصبح قيمة \(D(R)\) معروفة، يكون الجواب النهائي هو \(nP-D(R)\). إحدى التطبيقات تقارن هذا الأسلوب السريع مع برنامج ديناميكي دقيق على حالات صغيرة جدًا، لكن الحساب النهائي نفسه يعتمد فقط على صياغة أقصر مسار.
يحتوي رسم البواقي على \(k\) رؤوس و\(k(k-1)\) ضلعًا موجهًا، مع توليد الأضلاع ضمنيًا عند الحاجة. تشغيل Dijkstra على هذا الرسم الكثيف يكلف
$$O(k^2\log k)$$
زمنًا عند استخدام heap ثنائي.
أما مرحلة الغربال فتستخدم حدًا أعلى \(B\) من رتبة \(k(\log k+\log\log k)\)، ولذلك تكون كلفة توليد الأوليات \(O(B\log\log B)\) زمنًا و\(O(B)\) ذاكرة. وبالنسبة إلى القيم الفعلية، فإن مرحلة أقصر مسار هي المسيطرة.
المصفوفات الدائمة التي تحفظ الأوليات والخسائر والمسافات النهائية تحتاج إلى \(O(k)\) ذاكرة. وإذا استُخدم تنفيذ قياسي لـ Dijkstra يضيف مرشحًا جديدًا إلى heap كلما تحسنت مسافة، فقد ينمو heap نفسه في أسوأ الحالات حتى \(O(k^2)\) عنصرًا.